题目
转换问题:所有人把钱放在桌上,每个人拿走自己所需的钱。
-
每个人并不需要重复的把相同钞票放在桌子上再拿回来,因此对于第 i i i 种钞票,假设 Alice 初始有 x x x 张,结束有 x ′ x' x′ 张,Alice 只需拿或者放 ∣ x ′ − x ∣ |x'-x| ∣x′−x∣ 张。
-
对于第 i i i 钞票,人与人之间的交换次数等于拿放次数和的一半,比如 Alice 放 x x x 张,Bob 拿 x x x 张,被视为交换 x x x 张。
-
钱的总和不会变。
问题已经相当简单了,考虑搜索:前 i i i 种钞票,三个人各拿了 A , B , C A,B,C A,B,C 元:
int dfs(int i, int A, int B, int C)
{
if(A > sa or B > sb or C > sc) return 1e9;
// i = 6 时,A <= sa,B <= sb,C <= sc 而 A+B+C = sa+sb+sc 说明 A=sa,B=sb,C=sc,即最终状态
if(i == 6) return 0;
int res = 1e9;
// 对于第 i 种钞票,A 拿走 j 张,B 拿走 k 张,C 拿走剩下的
for(int j=0; j <= a[i]+b[i]+c[i]; j++)
for(int k=0; j + k <= a[i]+b[i]+c[i]; k++)
{
res = min(res, dfs(i+1, A+j*w[i], B+k*w[i], C+(a[i]+b[i]+c[i]-j-k)*w[i]) + abs(j-a[i])+abs(k-b[i])+abs(a[i]+b[i]-j-k) );
}
return res;
}
int main()
{
cin >> x1 >> x2 >> x3;
for(int i=0; i<6; i++) cin >> a[i], sa += a[i] * w[i];
for(int i=0; i<6; i++) cin >> b[i], sb += b[i] * w[i];
for(int i=0; i<6; i++) cin >> c[i], sc += c[i] * w[i];
sa = sa - x1 + x3, sb = sb - x2 + x1, sc = sc - x3 + x2;
int ans = dfs(0, 0, 0, 0);
if(ans < 1e9) cout << ans / 2;
else cout << "impossible";
}
根据钱的总和不变,当 A , B A,B A,B 固定时, C C C 也是固定的,因此状态数至多为 6 × 1000 × 1000 6 \times 1000 \times 1000 6×1000×1000 ,考虑记忆化搜索。