周年纪念晚会（没有上司的舞会）
1 #include<bits/stdc++.h> 2 #define N 6005 3 using namespace std; 4 int n,root,hp[N],f[N][2]; 5 bool vis[N]; 6 vector<int> son[N]; 7 inline int read() { 8 int x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 10 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 11 return x*f; 12 } 13 14 void dp(int x) { 15 f[x][1]=hp[x]; 16 for(int i=0;i<son[x].size();i++) { 17 int y=son[x][i]; 18 dp(y); 19 f[x][0]+=max(f[y][1],f[y][0]); 20 f[x][1]+=f[y][0]; 21 } 22 } 23 24 int main() { 25 memset(vis,0,sizeof(vis)); 26 n=read(); 27 for(int i=1;i<=n;i++) hp[i]=read(); 28 for(int i=1;i<n;i++) { 29 int l=read(),k=read(); 30 son[k].push_back(l); vis[l]=1; 31 } 32 for(int i=1;i<=n;i++) 33 if(!vis[i]) {root=i; break;} 34 dp(root); 35 printf("%d",max(f[root][1],f[root][0])); 36 return 0; 37 } 38 /* 39 树形DP入门题 40 设f[i][0]表示第i个人不去所能获得的最大值 41 f[i][1]表示第i个人去所能获得的最大值 42 方程如题意所示。 43 f[i][0]=sum(max(f[son][1],f[son][0])); 下属去不去随意 44 f[i][1]=hp[i]+sum(f[son][0]); 加上快乐值，下属只能不去 45 */
选课
1 #include<bits/stdc++.h> 2 #define N 1005 3 using namespace std; 4 int n,m,f[N][N],fro[N],cnt; 5 struct edge{int to,nxt;}e[N]; 6 void add(int x,int y) { 7 e[++cnt].to=y; e[cnt].nxt=fro[x]; fro[x]=cnt; 8 } 9 10 void dp(int x) { 11 for(int i=fro[x];i!=0;i=e[i].nxt) { 12 int to=e[i].to; 13 dp(to); 14 for(int j=m+1;j>=1;j--) 15 for(int k=0;k<j;k++) 16 f[x][j]=max(f[x][j],f[to][k]+f[x][j-k]); 17 } 18 } 19 20 int main() { 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=n;i++) { 23 int fa; scanf("%d",&fa); 24 add(fa,i); 25 scanf("%d",&f[i][1]); 26 } 27 dp(0); 28 printf("%d",f[0][m+1]); 29 return 0; 30 } 31 /* 32 树形DP 33 f[i][j]表示以i为根节点选j门课的最优值。 34 01背包的思想优化空间。 35 把0号节点看做根节点，列入必选的范围，即要选m+1门课。 36 （森林---->树） 37 */
二叉苹果树
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,q,cnt,f[105][105],fro[105],sum[105]; 4 struct edge{int to,v,nxt;}e[205]; 5 inline int read() { 6 int x=0,f=1; char c=getchar(); 7 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 8 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 9 return x*f; 10 } 11 void add(int x,int y,int z) { 12 e[++cnt].to=y,e[cnt].v=z,e[cnt].nxt=fro[x]; fro[x]=cnt; 13 } 14 15 void dp(int x,int fa) { 16 for(int i=fro[x];i;i=e[i].nxt) { 17 int y=e[i].to; 18 if(y==fa) continue; 19 dp(y,x); 20 sum[x]+=sum[y]+1; //统计目前深搜过的边数 21 for(int j=sum[x];j>0;j--) //01背包的思想优化空间 22 for(int k=0;k<j;k++) 23 f[x][j]=max(f[x][j],f[x][j-k-1]+f[y][k]+e[i].v); //注意边的细节 24 } 25 } 26 27 int main() { 28 n=read(),q=read(); 29 for(int i=1;i<n;i++) { 30 int x=read(),y=read(),z=read(); 31 add(x,y,z); add(y,x,z); 32 } 33 dp(1,0); 34 printf("%d",f[1][q]); 35 } 36 /* 37 树形DP 38 思路类似【选课】(见上) 39 */
数字转换
1 #include<bits/stdc++.h> 2 #define N 50005 3 using namespace std; 4 int n,sum[N],d1[N],d2[N]; 5 6 int main() { 7 scanf("%d",&n); 8 for(int i=1;i<=n;i++) //预处理约数和 9 for(int j=2;j<=n/i;j++) sum[i*j]+=i; 10 for(int i=n;i>=1;i--) //i的父亲(sum[i])一定比i小,所以n~1枚举i 11 if(sum[i]<i) 12 if(d1[i]+1>d1[sum[i]]) { 13 d2[sum[i]]=d1[sum[i]]; 14 d1[sum[i]]=d1[i]+1; 15 } 16 else if(d1[i]+1>d2[sum[i]]) d2[sum[i]]=d1[i]+1; 17 int ans=0; 18 for(int i=1;i<=n;i++) ans=max(ans,d1[i]+d2[i]); 19 printf("%d",ans); 20 } 21 /* 22 树形DP 23 预处理出小于等于N的每个数的约数和sum[i]。 24 如果sum[i]<i，那么i和sum[i]可以互相转化。 25 即两点间连一条边,i为sum[i]的一个儿子。 26 最后的结果是一棵树，问题就转化为求这棵树的直径。 27 */
旅游规划
1 #include<bits/stdc++.h> 2 #define N 200003 3 using namespace std; 4 int fro[N],cnt,n,ans=0,f[N],s[N]; //f[i]是以i为根的最长链，s[i]是次长链 5 struct node{int to,nxt;}a[N<<1]; 6 inline int read() { 7 int x=0,f=1; char c=getchar(); 8 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 9 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 10 return x*f; 11 } 12 void add(int x,int y) { 13 a[++cnt].to=y; a[cnt].nxt=fro[x]; fro[x]=cnt; 14 } 15 16 int dfs1(int u,int fa) { //寻找子树中的最长链和次长链 17 for(int i=fro[u];i!=0;i=a[i].nxt) { 18 int to=a[i].to; 19 if(to==fa) continue; 20 dfs1(to,u); 21 if(f[to]+1>f[u]) s[u]=f[u],f[u]=f[to]+1; //更新最长链（把原来最长链的值赋给次长链） 22 else if(f[to]+1>s[u]) s[u]=f[to]+1; //更新次长链 23 } 24 } 25 26 void dfs2(int u,int fa,int dis) { //搜索u上面的最长链（用dis表示），更新f[u]和s[u] 27 /* 28 因为f[i]和s[i]的值由子树转移 29 所以就忽略了上面的最长链 30 */ 31 for(int i=fro[u];i!=0;i=a[i].nxt) { 32 int to=a[i].to; 33 if(to==fa) continue; 34 if(f[to]+1==f[u]) dfs2(to,u,max(dis+1,s[u]+1)); //如果to已经在u的子树最长链上 35 else dfs2(to,u,max(dis+1,f[u]+1)); 36 } 37 if(dis>f[u]) s[u]=f[u],f[u]=dis; //更新 38 else if(dis>s[u]) s[u]=dis; 39 } 40 41 int main() { 42 n=read(); 43 for(int i=1;i<n;i++) { 44 int x=read()+1,y=read()+1; 45 add(x,y); add(y,x); 46 } 47 dfs1(1,1); 48 dfs2(1,1,0); 49 for(int i=1;i<=n;i++) ans=max(ans,f[i]+s[i]); //因为最长链和次长链从不同位置转移，所以树上最长链为两个的和 50 for(int i=1;i<=n;i++) 51 if(f[i]+s[i]==ans) printf("%d ",i-1); 52 return 0; 53 } 54 //树形DP
骑士
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define N 1000001 4 using namespace std; 5 int n,cnt,fa[N]; 6 ll ans,fight[N],fro[N],f[N][2]; 7 bool use[N]; 8 struct edge{int to,nxt;}e[N]; 9 inline int read() { 10 int x=0,f=1; char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 12 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 13 return x*f; 14 } 15 ll mmax(ll x,ll y) {return x>y?x:y;} 16 void add(int x,int y) { 17 e[++cnt].to=y; e[cnt].nxt=fro[x]; fro[x]=cnt; 18 } 19 20 void dfs(int x,int r) { 21 use[x]=1; 22 f[x][1]=fight[x]; 23 f[x][0]=0; 24 for(int i=fro[x];i!=0;i=e[i].nxt) { 25 int to=e[i].to; 26 if(to!=r) { 27 dfs(to,r); 28 f[x][1]+=f[to][0]; 29 f[x][0]+=mmax(f[to][0],f[to][1]); 30 } 31 else f[to][1]=-100000000; 32 } 33 } 34 35 void find(int x) { 36 while(!use[x]) use[x]=1,x=fa[x]; 37 dfs(x,x); 38 ll hh=f[x][0]; 39 x=fa[x]; 40 dfs(x,x); 41 ans+=mmax(hh,f[x][0]); 42 } 43 44 int main() { 45 n=read(); 46 for(int i=1;i<=n;i++) { 47 scanf("%lld",&fight[i]); int y=read(); 48 add(y,i); fa[i]=y; 49 } 50 for(int i=1;i<=n;i++) 51 if(!use[i]) find(i); 52 printf("%lld",ans); 53 return 0; 54 } 55 /* 56 树形DP 57 【没有上司的舞会】加难版。有多个联通块，每个联通块都是一个基环树。 58 把每个联通块的环上删一条边，删掉的边所连接的两点 x y，不能同时选。 59 所以我们分别强制 x y 其中一个点不选，对新树深搜。 60 状态转移方程同【没有上司的舞会】（见上） 61 */
皇宫看守
1 #include<bits/stdc++.h> 2 #define N 1505 3 #define INF 0x3f3f3f3f 4 using namespace std; 5 int fro[N],cnt,n,f[N][3]; 6 struct node{int to,nxt;}a[N<<1]; 7 inline int read() { 8 int x=0,f=1; char c=getchar(); 9 while(c<'0'||c>'9') {if(c=='-')f=-1; c=getchar();} 10 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 11 return x*f; 12 } 13 void add(int x,int y) { 14 a[++cnt].to=y; a[cnt].nxt=fro[x]; fro[x]=cnt; 15 } 16 17 void dfs(int u,int fa) { 18 int hh=INF; 19 for(int i=fro[u];i!=0;i=a[i].nxt) { 20 int y=a[i].to; 21 if(y!=fa) { 22 dfs(y,u); 23 f[u][0]+=min(f[y][1],f[y][2]); 24 f[u][1]+=min(f[y][1],f[y][2]); 25 hh=min(hh,f[y][2]-min(f[y][1],f[y][2])); 26 f[u][2]+=min(f[y][0],min(f[y][1],f[y][2])); 27 } 28 } 29 f[u][1]+=hh; 30 } 31 32 int main() { 33 n=read(); 34 for(int i=1;i<=n;i++) { 35 int x=read(); f[x][2]=read(); 36 int m=read(); 37 for(int j=1;j<=m;j++) { 38 int y=read(); 39 add(x,y); add(y,x); 40 } 41 } 42 dfs(1,0); 43 printf("%d",min(f[1][1],f[1][2])); 44 return 0; 45 } 46 /* 47 树形DP 48 f[i][0]:父亲守卫自己（儿子们只要不让自己守护就行） 49 f[i][1]:儿子守卫自己（儿子们不让自己守护，并强制一个儿子自己守护自己） 50 f[i][2]:自己守卫自己（儿子们怎么样都行） 51 */
战略游戏
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,cnt,fro[1505],f[1505][2]; 4 struct edge{int to,nxt;}e[3005]; 5 inline int read() { 6 int x=0; char c=getchar(); 7 while(c<'0'||c>'9') c=getchar(); 8 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 9 return x; 10 } 11 void add(int x,int y) { 12 e[++cnt].to=y,e[cnt].nxt=fro[x]; fro[x]=cnt; 13 } 14 15 void dfs(int x,int fa) { 16 f[x][1]=1; 17 for(int i=fro[x];i;i=e[i].nxt) { 18 int y=e[i].to; 19 if(y==fa) continue; 20 dfs(y,x); 21 f[x][1]+=min(f[y][0],f[y][1]); 22 f[x][0]+=f[y][1]; 23 } 24 } 25 26 int main() { 27 n=read(); 28 for(int i=1;i<=n;i++) { 29 int x=read()+1,k=read(); 30 for(int j=1;j<=k;j++) { 31 int y=read()+1; 32 add(x,y); add(y,x); 33 } 34 } 35 dfs(1,0); 36 printf("%d",min(f[1][1],f[1][0])); 37 } 38 /* 39 树形DP 40 f[x][0]：在x节点不放置士兵的最小值 41 f[x][1]：在x节点放置士兵的最小值 42 */
加分二叉树
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,f[40][40],root[40][40]; 4 inline int read() { 5 int x=0; char c=getchar(); 6 while(c<'0'||c>'9') c=getchar(); 7 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 8 return x; 9 } 10 11 void print(int l,int r) { //递归输出前序遍历 12 if(l>r) return ; 13 printf("%d ",root[l][r]); 14 print(l,root[l][r]-1); 15 print(root[l][r]+1,r); 16 } 17 18 int main() { 19 n=read(); 20 for(int i=1;i<=n;i++) { 21 f[i][i]=read(),root[i][i]=i; 22 f[i][i-1]=1; //空子树加分为1 23 } 24 for(int i=2;i<=n;i++) 25 for(int l=1;l+i-1<=n;l++) { 26 int r=l+i-1; 27 for(int k=l;k<=r;k++) //枚举根的位置 28 if(f[l][r]<f[l][k-1]*f[k+1][r]+f[k][k]) { 29 f[l][r]=f[l][k-1]*f[k+1][r]+f[k][k]; 30 root[l][r]=k; //记录根的位置 31 } 32 } 33 printf("%d ",f[1][n]); 34 print(1,n); 35 } 36 //乱入的区间DP 37 //f[i][j]:节点i到节点j为树的最大加分
叶子的染色
1 #include<bits/stdc++.h> 2 #define N 10005 3 #define INF 0x3f3f3f3f 4 using namespace std; 5 int n,m,cnt,fro[N],du[N],c[N],f[N][N]; 6 struct edge{int to,nxt;}e[N<<1]; 7 inline int read() { 8 int x=0; char c=getchar(); 9 while(c<'0'||c>'9') c=getchar(); 10 while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); 11 return x; 12 } 13 void add(int x,int y) { 14 e[++cnt].to=y,e[cnt].nxt=fro[x]; fro[x]=cnt; 15 } 16 17 void dp(int x,int fa) { 18 if(du[x]==1&&fa) { //叶子节点只能染色为c[x] 19 f[x][c[x]]=1,f[x][c[x]^1]=INF; 20 return; 21 } 22 f[x][1]=f[x][0]=1; 23 for(int i=fro[x];i;i=e[i].nxt) { 24 int y=e[i].to; 25 if(y==fa) continue; 26 dp(y,x); 27 f[x][1]+=min(f[y][1]-1,f[y][0]); //x与y染相同颜色就取消y的染色 28 f[x][0]+=min(f[y][1],f[y][0]-1); 29 } 30 } 31 32 int main() { 33 m=read(),n=read(); 34 for(int i=1;i<=n;i++) c[i]=read(); 35 for(int i=1;i<m;i++) { 36 int x=read(),y=read(); 37 add(x,y); add(y,x); 38 du[x]++,du[y]++; 39 } 40 dp(n+1,0); 41 printf("%d",min(f[n+1][1],f[n+1][0])); 42 } 43 /* 44 树形DP 45 f[x][0]表示x节点着以黑色的最小值 46 f[x][1]表示x节点着以白色的最小值 47 */
完结 ≧▽≦ （2018.12.31）