https://www.luogu.org/PRoblem/show?pid=1270 這題好像就是來考建圖吧 比如樣例嘛，把他搞成這樣子 
*2是因為要走過去再再走回來 5就是一幅畫； 然后直接dp就好啦； 建議先做p1273
我以為就這么結(jié)束了，但是洛谷有個好人，搞了一個變題啊，蠻好； https://www.luogu.org/problem/show?pid=3360 這一題中，每幅畫的價值不是1，而是一個數(shù)，而且可以很大； 而我一開始的數(shù)組 f[i][j]表示第i個節(jié)點再其子節(jié)點里找j個所需最少時間； 如果直接把這個程序放到這里來，那么變成 f[i][j]表示第i個節(jié)點再其子節(jié)點里找j的價值的畫個所需最少時間； 但是j會很大大大； 所以gg了； 那我們怎么搞呢？ f[i][j]表示第i個點（不包括自己）j秒時最大價值； ps:正因為不包括自己，所以最后根節(jié)點的時間時沒有算過的； 本來以為不會做了的，結(jié)果還是做出來了； 雖然時空復(fù)雜度略高，但是比看題解的人好多了； 我比較喜歡離線，所以先建圖再dp 還有這種dp，轉(zhuǎn)移方程就是枚舉其子節(jié)點所要的值，然后注意搜索順序和循環(huán)的順序就好了； 正如這里，我們先枚舉根節(jié)點的總時間(i)，然后枚舉某子節(jié)點的占用的時間(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);}很多時候，其實我們能夠自己做題的；
新聞熱點
疑難解答
