树形dp-P1270 “访问”美术馆P3360 偷天换日

2019-11-08 02:02:33

字体：大中小

来源：转载

供稿：网友

https://www.luogu.org/PRoblem/show?pid=1270 这题好像就是来考建图吧比如样例嘛，把他搞成这样子这里写图片描述 *2是因为要走过去再再走回来 5就是一幅画；然后直接dp就好啦；建议先做p1273

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;struct cs{ int to,next,vv;}a[200001];int head[100001],f[1000][2001],w[1000];int m,n,x,y,z,ll;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}void dfs1(int y){ n++;int nn=n; init(y,n); scanf("%d%d",&x,&y); w[n]=x*2; if(y){ for(int i=1;i<=y;i++)init(nn,++n); } if(!y)dfs1(nn),dfs1(nn);}int dfs(int x){ f[x][0]=0; if(!head[x]){ f[x][1]=5;return 1; } int sum=0,son; for(int k=head[x];k;k=a[k].next){ son=dfs(a[k].to); sum+=son; for(int j=sum;j;j--) for(int i=1;i<=son;i++) if(j-i>=0) f[x][j]=min(f[x][j],f[x][j-i]+f[a[k].to][i]+w[a[k].to]); } return sum;}int main(){ memset(f,63,sizeof f); scanf("%d",&m); dfs1(-1); z=dfs(1); for(int i=z;i>=0;i--)if(f[1][i]<=m-w[1]-1){printf("%d",i);return 0;}//m要-1，因为是警察来之前 /* for(int i=1;i<=n;i++){ for(int j=1;j<=z;j++)cout<<i<<' '<<j<<' '<<f[i][j]<<endl; }*/}

我以为就这么结束了，但是洛谷有个好人，搞了一个变题啊，蛮好； https://www.luogu.org/problem/show?pid=3360 这一题中，每幅画的价值不是1，而是一个数，而且可以很大；而我一开始的数组 f[i][j]表示第i个节点再其子节点里找j个所需最少时间；如果直接把这个程序放到这里来，那么变成 f[i][j]表示第i个节点再其子节点里找j的价值的画个所需最少时间；但是j会很大大大；所以gg了；那我们怎么搞呢？ f[i][j]表示第i个点（不包括自己）j秒时最大价值； ps:正因为不包括自己，所以最后根节点的时间时没有算过的；本来以为不会做了的，结果还是做出来了；虽然时空复杂度略高，但是比看题解的人好多了；我比较喜欢离线，所以先建图再dp 还有这种dp，转移方程就是枚举其子节点所要的值，然后注意搜索顺序和循环的顺序就好了；正如这里，我们先枚举根节点的总时间(i)，然后枚举某子节点的占用的时间(j)； f[x][i]=max(f[x][i],f[x][i-j]+f[a[k].to][j-w[a[k].to]]);

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;struct cs{ int to,next,vv;}a[200001];int head[100001],f[601][601],w[601],c[601];int m,n,x,y,z,ll,ans;void init(int x,int y){ ll++; a[ll].to=y; a[ll].next=head[x]; head[x]=ll;}void dfs1(int y){ n++;int nn=n; init(y,n); scanf("%d%d",&x,&y); w[n]=x*2; if(y){ int yy=y; for(int i=1;i<=yy;i++){ init(nn,++n); scanf("%d%d",&x,&y); c[n]=x;w[n]=y; } }else dfs1(nn),dfs1(nn);}void dfs(int x){ if(!head[x]){ f[x][0]=c[x];return; } for(int k=head[x];k;k=a[k].next){ dfs(a[k].to); for(int i=600;i;i--) for(int j=w[a[k].to];j<=i;j++) f[x][i]=max(f[x][i],f[x][i-j]+f[a[k].to][j-w[a[k].to]]); }}int main(){ scanf("%d",&m); dfs1(-1); dfs(1); for(int i=0;i<=m-1-w[1];i++)ans=max(ans,f[1][i]); printf("%d",ans);}

很多时候，其实我们能够自己做题的；

上一篇：LeetCode 35. Search Insert Position

下一篇：剑指offer经典编程（十五）