[DP] Codeforces Round #197 (Div. 2) C. Xenia and Weights

本文主要是介绍[DP] Codeforces Round #197 (Div. 2) C. Xenia and Weights，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接： http://codeforces.com/contest/339/problem/C

DFS DP  方法都可解，DFS没什么可说的

DP时 设 一个 3维dp[i][j][k] 表示 第i 次 放砝码（一共m次） ，此次放的是 j 这个重量的砝码（如果有）， 放完是 k 这个重量差（此次放的这个盘比另一个重),  这个数组的值表示达到当前状态 的上一次 （即第i-1次） 放的砝码重量。

由dp[i][j][k] 可得到  dp[i+1][t][t-k]=j; ( t 这个重量存在&& t-k>0 && t!=j) 

DP code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1000000000
#define M 1004
int m,dp[M][12][12];
char str[13];
void dfs(int x,int y,int z)
{if(x<=0) return ;dfs(x-1,dp[x][y][z],y-z);printf("%d ",y);//搞了半天是  递归函数里面的顺序 弄错了。。
}
int main()
{scanf("%s",str+1);scanf("%d",&m);memset(dp,-1,sizeof(dp));for(int i=0;i<=10;i++){if(str[i]=='0') continue;dp[1][i][i]=0;}for(int i=2;i<=m;i++){for(int j=1;j<=10;j++){for(int k=1;k<=10;k++){if(dp[i-1][j][k]<0) continue;for(int t=1;t<=10;t++){if(str[t]=='0') continue;if(t==j) continue;if(t<=k) continue;dp[i][t][t-k]=j;}}}}int flag=0;for(int i=1;i<=10;i++){if(flag) break;for(int j=1;j<=10;j++){if(flag) break;if(dp[m][i][j]>=0){flag=1;printf("YES\n");dfs(m,i,j);}}}if(!flag)  printf("NO\n");return 0;
}

DFS code 

//dfs  ..
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1000000000
#define M 1005
int m,b[1010],flag;
char a[14];
void dfs(int x,int p,int aa,int bb)
{if(flag) return ;if(x>m){flag=1; printf("YES\n");for(int i=1;i<=m;i++) printf("%d ",b[i]);puts("");}if(x%2){for(int i=1;i<=10;i++){if(a[i]=='1' && aa+i>bb && p!=i){// printf("%d ....\n",i);b[x]=i;dfs(x+1,i,aa+i,bb);}}}else{for(int i=1;i<=10;i++){if(a[i]=='1' && i!=p && bb+i>aa){b[x]=i;dfs(x+1,i,aa,bb+i);}}}
}
int main()
{//freopen("in.txt","r",stdin);scanf("%s",a+1);scanf("%d",&m);flag=0;dfs(1,-1,0,0);if(!flag) printf("NO\n");return 0;
}

这篇关于[DP] Codeforces Round #197 (Div. 2) C. Xenia and Weights的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---