CodeForces 339C Xenia and Weights (简单dfs/dp)

题意：

现有类似砝码的东西，重量在1~10。现在有一个天平，开始两边没东西，现在先往左边，再到右边，又到左边……放砝码。要求每次所放的那一边，重量总和要比另一边大。

求出能满足条件的放砝码的序列。

思路：

简单dfs。

看当前这步放这个是否满足，满足则继续dfs下去，不满足就枚举下一个。

（这题也有dp的做法。后面再补）

code：

#include <bits/stdc++.h>
using namespace std;
char ch[15];
int a[15], m, cnt;
int res[1005];
bool dfs(int sum, int count, int pre) {
if(count == m+1) {
puts("YES");
for(int i = 1;i <= m; i++)
printf("%d%c", res[i], i==m?'n':' ');
return true;
}
for(int i = 0;i < cnt; i++) {
if(i == pre) continue;
if((count&1) && sum + a[i] > 0) {
res[count] = a[i];
if(dfs(sum+a[i], count+1, i)) return true;
}
else if(!(count&1) && sum - a[i] < 0) {
res[count] = a[i];
if(dfs(sum-a[i], count+1, i)) return true;
}
}
return false;
}
int main() {
scanf("%s%d", ch, &m);
for(int i = 0;i < 10; i++)
if(ch[i] == '1') a[cnt++] = i+1;
if(!dfs(0, 1, -1)) puts("NO");
return 0;
}

最后

以上就是和谐便当为你收集整理的CodeForces 339C Xenia and Weights (简单dfs/dp)的全部内容，希望文章能够帮你解决CodeForces 339C Xenia and Weights (简单dfs/dp)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。