-
Tree of Tree (树形DP)
VJ链接:https://vjudge.net/problem/ZOJ-3201
大概写了一下树形DP入门题,入门题套路都在搜到叶子节点然后处理子树。。
确定DP转移方程时注意b要正序a要倒序,
如k=5,假设这时算到第i(>1)个子树,此时dp[u][5]中存的是利用其他子树构造出的最大树,
利用此子节点更新父节点(父节点中“腾”出位置给该子树),
如果a正序,那么dp[u][2+b]=dp[u][2]+dp[v][b]时,dp[u][2](已经计算过)值代表的树中可能已经有该子节点,此时dp[v][b]中也包含该子节点,明显是错误的状态。
如果a 倒序,dp[u][2+b]=dp[u][2]+dp[v][b],此时dp[u][2](未计算过)仍然表示由其他子节点构成的树,用该树再加子树才是正确状态。
发现写码迷的地方写出来题解就很清楚了。)
#include<map> #include<set> #include<queue> #include<cmath> #include<stack> #include<ctime> #include<cstdio> #include<vector> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; #define pi acos(-1.0) #define INF 0x3f3f3f3f #define mod 1000000009 #define endll printf("\n") #define s1(a) scanf("%d",&a) #define lowbit(x) ((x)&(-x)) #define s2(a,b) scanf("%d %d",&a,&b) #define mem(a,b) memset(a,b,sizeof(a)) #define s3(a,b,c) scanf("%d %d %d",&a,&b,&c) int n,k,tot; int a[111]; // int head[111]; struct IN { int v; int nex; IN(){}IN(int vv,int nn){v=vv,nex=nn;} }edge[MAXN]; int dp[111][111]; int ans; void dfs(int x,int fa) { for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].v; if(v==fa) continue; dfs(v,x); for(int a=k-1;a>0;a--) for(int b=1;a+b<=k;b++) dp[x][a+b]=max(dp[x][a+b],dp[x][a]+dp[v][b]); } ans=max(ans,dp[x][k]); } int main() { while(~s2(n,k)) { tot=0;mem(head,0); ans=0;mem(dp,0); for(int i=1;i<=n;i++) s1(dp[i][1]); for(int i=1;i<n;i++) { int u,v;s2(u,v);u++;v++; edge[++tot]=IN(v,head[u]);head[u]=tot; edge[++tot]=IN(u,head[v]);head[v]=tot; } dfs(1,0); printf("%d\n",ans); } return 0; }
-
Dividing the Path (单调队列优化)
VJ链接:https://vjudge.net/problem/POJ-2373
类似这样的转移方程可以用到单调队列: f[i]=max(f[j])+w[i](其中max中的f[i]有固定范围)
大致流程:
1、先删掉前面超出范围的队头。
2、利用队头转移。
3、将这个数和队尾比较,若队尾不比它优,就删掉队尾,直到队列为空或队尾比它优。最后将它加进队尾。
2、利用队头转移。
3、将这个数和队尾比较,若队尾不比它优,就删掉队尾,直到队列为空或队尾比它优。最后将它加进队尾。
#include<map> #include<set> #include<queue> #include<cmath> #include<stack> #include<ctime> #include<cstdio> #include<vector> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<cassert> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e6+10; #define pi acos(-1.0) #define INF 0x3f3f3f3f #define mod 1000000009 #define endll printf("\n") #define s1(a) scanf("%d",&a) #define lowbit(x) ((x)&(-x)) #define s2(a,b) scanf("%d %d",&a,&b) #define mem(a,b) memset(a,b,sizeof(a)) #define s3(a,b,c) scanf("%d %d %d",&a,&b,&c) int n,l,a,b; int mp[MAXN]; int dp[MAXN];//0到i位置的最小数目,i应为偶数 //dp[i]=min(dp[j])+1,j在(i-2*B,i-2*A)之间; //i,j位置无奶牛,i>=2*a int que[MAXN];//存储下标 int main() { s2(n,l);s2(a,b); for(int i=0;i<=l;i++) {mp[i]=0;dp[i]=INF;} for(int i=0,s,e;i<n;i++) { s2(s,e); for(int j=s+1;j<e;j++) //注意端点重复不算重复 mp[j]=1; } dp[0]=0; int head=0,tail=0; for(int i=2*a;i<=l;i+=2) { while (head<tail && que[head]<i-2*b)//超过范围 head++; while (head<tail && dp[que[tail-1]]>=dp[i-2*a])//答案更优 tail--; que[tail++]=i-2*a; if (dp[que[head]]!=INF&&!mp[i]) dp[i]=dp[que[head]]+1; } if(dp[l]==INF) dp[l]=-1; printf("%d\n",dp[l]); return 0; }