Luogu P1272 重建道路树形DP

刚才瞅了半天自己当初写的，终于瞅出来了。。。QWQ

设f[i][j]表示以i为根的子树，包含j个节点所需砍掉的最小边数

那么可知f[u][1]=u的度；

方程：f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-2);

为何减2？因为你已经默认了把与自己相连的所有边都去掉了，于是相当于多去了边(u,v)两次，所以要-2

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define R register int
using namespace std;
const int Inf=0x3f3f3f3f,N=201;
struct edge{
    int v,nxt;
}e[N<<1];
int n,m,ans=Inf,cnt;
int r[N],fir[N],f[N][N];
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=(ret<<3)+(ret<<1)+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
inline void add(int u,int v) {e[++cnt].v=v,e[cnt].nxt=fir[u],fir[u]=cnt;}
void dfs(int u,int fa) {
    f[u][1]=r[u];
    for(R i=fir[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v) {
        if(v!=fa) {
            dfs(v,u); for(R j=m;j>=1;j--) 
                for(R k=1;k<=j;k++) f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]-2);
        }
    } ans=min(f[u][m],ans);
}
signed main() {
    n=g(),m=g();memset(f,0x3f,sizeof(f));
    for(R i=1;i<n;i++) {R u=g(),v=g(); add(u,v),add(v,u); r[u]++,r[v]++;}
    dfs(1,0); printf("%d
",ans);
}

2019.04.28

Luogu P1272 重建道路 树形DP

Luogu P1272 重建道路树形DP