首页 > 代码库 > noip Dynamic Programming
noip Dynamic Programming
A - Jury Compromise
题意：
有n(<=200)个人作为陪审团的被选举成员,分别有正方和反方给予的评价,要求在这n个人中选出m(<=20)个人,在保证正方评价之和与反方评价之和差最小的情况下,使得评价分数总和最高。
题解：
0.定义状态fi][k]当前已经选取了i个人并且这i个人的差值为k时的评分总和的最大值,p[i][k]当前已经选取了i个人并且这i个人的差值为k时第i个人的编号。
1.如果令c[i]表示第i个人正方与反方的差,s[i]表示第i个人正方与反方的和,那么状态转移f[i][k+c[j]] = f[i-1][k]+s[j],p[i][k+c[j]] = j 条件:f[i][k+c[j]] < f[i-1][c[j]]+s[j]&&当前选的这第i个人(j)没有被选过.边界为dp[0][0] = 0;
2.但是下标的差值有可能为负数,那么下标总体往右平移就好了,最后再找出差值最小的dp状态,那么正方的总和为(dp[m][c]+c)/2,反方即为(dp[m][c]-c)/2
代码：
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1e3+7;int kase = 0,n,m,c[N],a[N],b[N],s[N],d[N][N],p[N][N],ret[N];bool select(int i,int k,int x,int c[]){ while(i && p[i][k] != x)k -= c[p[i][k]],--i; return i;}void print(int i,int k,int c[]){ while(i)ret[i] = p[i][k],k -= c[p[i][k]],--i; sort(ret+1,ret+1+m); for(int i = 1;i <= m;++i)printf("%d ",ret[i]); cout<<endl<<endl;}int main(){ while(scanf("%d%d",&n,&m) != EOF && n && m){ memset(d,-1,sizeof(d)); memset(p,-1,sizeof(p)); for(int i = 1;i <= n;++i){ scanf("%d%d",&a[i],&b[i]); c[i] = a[i]-b[i],s[i] = a[i]+b[i]; } int M = 20*m; d[0][M] = 0; for(int i = 1;i <= m;++i){ for(int k = 0;k <= 2*M;++k)if(d[i-1][k]>=0){ for(int j = 1;j <= n;++j)if(d[i][k+c[j]]<d[i-1][k]+s[j] && !select(i-1,k,j,c)){ p[i][k+c[j]] = j; d[i][k+c[j]] = d[i-1][k]+s[j]; } } } int x; for(x = 0;x <= M;++x)if(d[m][M-x] >= 0 || d[m][M+x] >= 0)break; int minc = d[m][M-x]>d[m][M+x]?M-x:M+x; printf("Jury #%d\n",++kase); printf("Best jury has value %d for prosecution and value %d for defence:\n",(d[m][minc]+minc-M)>>1,(d[m][minc]-minc+M)>>1); print(m,minc,c); }}
B - Number Game
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 2e1+7;const int AS = (1<<21)-1;int dp[AS<<1],S,n,kase,ret[N],cnt,x[N];int update(int S,int x){ S |= 1<<x; for(int i = 2;i+x <= 20;++i)if(S&(1<<i))S |= 1<<i+x; return S;}int search(int S){ if(dp[S] != -1)return dp[S]; for(int i = 2;i <= 20;++i)if(!(S&(1<<i))){ int S0 = update(S,i); if(!search(S0))return dp[S] = 1; } return dp[S] = 0;}int main(){ while(scanf("%d",&n) && n){ memset(dp,-1,sizeof(dp)); S = AS,dp[AS] = 0,cnt = 0; for(int i = 0;i < n;++i)scanf("%d",&x[i]),S ^= 1<<x[i]; for(int i = 0;i < n;++i){ int S0 = update(S,x[i]); if(!search(S0))ret[++cnt] = x[i]; } printf("Test Case #%d\n",++kase); cnt ? printf("The winning moves are:") : printf("There‘s no winning move."); for(int i = 1;i <= cnt;++i)printf(" %d",ret[i]); cout<<endl<<endl; } return 0;}
C - Prison rearrangement
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 420;const int M = 40010;#define clr(a,b) memset(a,b,sizeof(a))int n,m,kase;int head[N],ecnt;struct edge{int v,nxt;}e[M<<1];void adde(int u,int v){e[ecnt] = (edge){v,head[u]};head[u] = ecnt++;}int vis[N],T;int dp[N][N],S0[N],S1[N];void pre(){ T = 0,clr(vis,0),clr(S0,0),clr(S1,0); ecnt = 0,clr(head,-1),clr(e,0),clr(dp,0);}void dfs(int u){ vis[u] = 1; u <= n ? S0[T] += 1 : S1[T] += 1; for(int it = head[u];it != -1;it = e[it].nxt)if(!vis[e[it].v])dfs(e[it].v);}int main(){ scanf("%d",&kase); while(kase--){ pre(); scanf("%d%d",&n,&m); for(int i = 1;i <= m;++i){ int u,v; scanf("%d%d",&u,&v);v += n; adde(u,v),adde(v,u); } for(int i = 1;i <= n<<1;++i)if(!vis[i])++T,dfs(i); dp[0][0] = 1; for(int k = 1;k <= T;++k){ for(int i = n>>1;i >= S0[k];--i){ for(int j = n>>1;j >= S1[k];--j){ dp[i][j] = dp[i][j] || dp[i-S0[k]][j-S1[k]]; } } } for(int i = n>>1;i >= 0;--i)if(dp[i][i]){ printf("%d\n",i);break; } } return 0;}
D - Clans on the Three Gorges
代码：
#include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <algorithm>using namespace std;const int N = 110;const int inf = 1e8;int n,m,k,A[N],B[N],C[N],kase;int dN[N][N],dM[N][N],dK[N][N];#define mini(a,b,c) min(min(a,b),c)int main(){ scanf("%d",&kase); while(kase--){ scanf("%d%d%d",&n,&m,&k); for(int i = 1;i <= n;++i)scanf("%d",&A[i]); for(int i = 1;i <= m;++i)scanf("%d",&B[i]); for(int i = 1;i <= k;++i)scanf("%d",&C[i]); for(int i = 0;i < N;++i) for(int j = 0;j < N;++j) dN[i][j] = dM[i][j] = dK[i][j] = inf; dN[n+1][0] = dM[m+1][0] = dK[k+1][0] = 0; for(int i = n;i >= 1;--i) for(int j = 1;j <= m;++j) dN[i][j] = mini(dN[i+1][j-1],dN[i+1][j],dN[i][j-1])+fabs(A[i]-B[j]); for(int i = m;i >= 1;--i) for(int j = 1;j <= k;++j) dM[i][j] = mini(dM[i+1][j-1],dM[i+1][j],dM[i][j-1])+fabs(B[i]-C[j]); for(int i = k;i >= 1;--i) for(int j = 1;j <= n;++j) dK[i][j] = mini(dK[i+1][j-1],dK[i+1][j],dK[i][j-1])+fabs(C[i]-A[j]); int ret = inf; for(int i = 0;i <= n+1;++i) for(int j = 0;j <= m+1;++j) for(int l = 0;l <= k+1;++l){ ret = min(ret,dN[i][j]+dM[j][l]+dK[l][i]); ret = min(ret,dN[i+1][j]+dM[j][l]+dK[l][i]); ret = min(ret,dN[i][j]+dM[j+1][l]+dK[l][i]); ret = min(ret,dN[i][j]+dM[j][l]+dK[l+1][i]); ret = min(ret,dN[i+1][j]+dM[j+1][l]+dK[l][i]); ret = min(ret,dN[i][j]+dM[j+1][l]+dK[l+1][i]); ret = min(ret,dN[i+1][j]+dM[j][l]+dK[l+1][i]); ret = min(ret,dN[i+1][j]+dM[j+1][l]+dK[l+1][i]); } cout<<ret<<endl; } return 0;}
E - Crossed Matchings
#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N = 1e3+7;int kase,n,m,dp[N][N],A[N],B[N];int main(){ scanf("%d",&kase); while(kase--){ scanf("%d%d",&n,&m); for(int i = 1;i <= n;++i)scanf("%d",&A[i]); for(int i = 1;i <= m;++i)scanf("%d",&B[i]); memset(dp,0,sizeof(dp)); for(int i = 2;i <= n;++i){ for(int j = 2;j <= m;++j){ dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if(A[i] == B[j])continue; int S0 = 0,S1 = 0; for(S0 = i-1;S0 >= 1;--S0)if(A[S0] == B[j])break; for(S1 = j-1;S1 >= 1;--S1)if(A[i] == B[S1])break; if(S0&&S1)dp[i][j] = max(dp[i][j],dp[S0-1][S1-1]+2); } } cout<<dp[n][m]<<endl; } return 0;}
F - SUBTRACT
定义一种操作,操作con{i}就是将a[i]-a[i+1]取出进行合并,再加入到a[i]的位置，a[i+1]消失,进行n-1次操作后,会剩下一个数字.给定长度为n(<=100)的数列及目标t（最后剩下的数字）,求操作顺序(Special Judge).
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1e2+7;const int M = 1e4+7;#define clr(a,b) memset(a,b,sizeof(a))int n,t,d[M],p[N][M],flag[N],ret[N],x[N];int main(){ while(scanf("%d%d",&n,&t) != EOF){ int sum = 0,cnt = 0; clr(d,0),clr(flag,0),clr(p,0); for(int i = 1;i <= n;++i)scanf("%d",&x[i]),sum += x[i],x[i]<<=1; t = t+sum-x[1]; for(int i = 3;i <= n;++i){ for(int j = t;j >= x[i];--j){ if(d[j] > d[j-x[i]]+x[i])p[i][j] = 0; else d[j]=d[j-x[i]]+x[i],p[i][j] = 1; } } int v = t; for(int i = n;i >= 3;--i)if(p[i][v])flag[i] = 1,v -= x[i]; for(int i = 3;i <= n;++i)if(flag[i])ret[++cnt] = i-1; for(int i = 0;i < cnt;++i)ret[i+1] -= i; for(int i = 1;i <= cnt;++i)printf("%d\n",ret[i]); for(int i = cnt+1;i < n;++i)puts("1"); } return 0;}
G - Special Experiment
有n(<=200)个原子和m(<=200)个光子，选出最大能量的原子集合,但是如果有任意两个原子的能力差等于一个光子的能量,那么这种方案是不行的。
题解：
0.如果两个原子的能量的差等于一个光子的能量,那么他们就面对选或是不选的情况,题目需要求最大能量的原子集合,那么是明显的树形dp(类似于"没有上司的舞会")
1.定义状态：dp[u][0/1]表示不选/选u这个节点的最大能量
2.状态转移：dp[u][0] += {max(dp[v][0],dp[v][1])}
dp[u][1] += {dp[v][0]}+w[u]
代码：
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1e3+47;int n,m,x,w[N],flag[1000000],ecnt,head[N],vis[N],dp[N][2];struct edge{int v,nxt;}e[N*N];#define clr(a,b) memset(a,b,sizeof(a))void adde(int u,int v){e[ecnt].v = v,e[ecnt].nxt = head[u],head[u] = ecnt++;}void search(int u){ vis[u] = 1; for(int it = head[u];it != -1;it = e[it].nxt)if(!vis[e[it].v]){ int v = e[it].v; search(v); dp[u][1] += dp[v][0]; dp[u][0] += max(dp[v][0],dp[v][1]); } dp[u][1] += w[u];}int main(){ while(scanf("%d%d",&n,&m) != EOF && n+m){ ecnt = 0; clr(vis,0),clr(dp,0),clr(head,-1),clr(flag,0); for(int i = 1;i <= n;++i)scanf("%d",&w[i]); for(int i = 1;i <= m;++i)scanf("%d",&x),flag[x] = 1; for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) if(flag[abs(w[i]-w[j])])adde(i,j); int ret = 0; for(int i = 1;i <= n;++i)if(!vis[i])search(i),ret += max(dp[i][0],dp[i][1]); cout<<ret<<endl; } return 0;}
H - Chores
#include <cstdio>#include <iostream>#include <algorithm>using namespace std;const int N = 1e5+7;int maxi,w,m,x,dp[N],n,ret;int main(){ scanf("%d",&n); for(int i = 1;i <= n;++i){ maxi = 0; scanf("%d%d",&w,&m); while(m--)scanf("%d",&x),maxi = max(maxi,dp[x]); dp[i] += maxi+w; } for(int i = 1;i <= n;++i)ret = max(ret,dp[i]); cout<<ret<<endl; return 0;}
noip Dynamic Programming
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。