题意
现在有一个天平,你拥有一些种类的砝码,这些砝码的重量均在 $1 \sim 10$ 间且对于每一种砝码你有无数多个。现在按照两个要求依次放置 $m$ 个砝码,要求如下:
- 相邻两次放置操作不能放置相同的砝码
- 每次放下砝码后必须保证放下砝码的这个盘的总重量大于另一盘。
其中第一个砝码必须放在左盘,第二个砝码必须放右盘,第三个放左盘,以此类推。
分析
直接 dfs 所有可能的方案,尝试将所有你拥有的砝码放入当前盘,并且按照两个要求进行剪枝。有一些细节,详见代码。
代码
#include <bits/stdc++.h>
using namespace std;
bool vis[11];
int record[1005]; //用来记录每轮放置的砝码重量
int m;
//五项参数分别表示当前轮到放到哪盘、左盘重量、右盘重量、已放置砝码数量、上一次放置的砝码重量
bool dfs(int turn, int left, int right, int times, int front) {
if (times)
if (turn) { //如果左右盘的重量并不满足要求2
if (left <= right)
return false;
} else if (left >= right)
return false;
if (times == m) { //如果已放置m个砝码
puts("YES");
for (int i = 0; i < times; i++)
printf("%d ", record[i]);
puts("");
return true;
}
bool check = false;
for (int i = 1; i <= 10; i++)
if (vis[i] && i != front) { //尝试所有可能放置的砝码,放入当前盘
record[times] = i;
if (!turn)
check |= dfs(!turn, left + i, right, times + 1, i);
else
check |= dfs(!turn, left, right + i, times + 1, i);
if (check) //一旦任意一种情况满足条件,则直接return
return true;
}
return check;
}
int main() {
int t;
scanf("%d", &t);
for (int i = 10; i; i--) { //拆分t
vis[i] = t % 10;
t /= 10;
}
scanf("%d", &m);
if (!dfs(0, 0, 0, 0, -1))
puts("NO");
return 0;
}
Comments | NOTHING