题解：P4026 [SHOI2008] 循环的债务
Super_Diu
·
·
题解
怎么没人讲转移方程啊。
题目要求我们求出交换钞票的最小次数，不难想到 dp。
初始化
设 dp_{t,i,j,k} 为处理完前 t 种面额，Alice 有 i 元，Bob 有 j 元，Cynthia 有 k 元时的最小交换次数。
总金额为 tot，三个人的金额为 s_{1\sim 3}。
推导
自然可以想到暴力枚举四维然后转移。但是时间复杂度来到了 \mathcal O(n^3)，考虑降维。
由于总金额在交换后不变，Alice 和 Bob 有 s_1+s_2 元，所以 Cynthia 自然就有 tot-(s_1+s_2) 元。
所以就能简化为：
初始状态：$dp_{0,s_1,s_2}=0$，其余为极大值。
但是转移方程怎么推？
首先，我们要枚举在状态 $(i,j,k)$ 时，可能交换的钞票 $x,y$。
其次，计算出交换 $x,y$ 后，A、B 的新总金额 $tx,ty$。显然，$tx=j-(a_{1,i}-x)\times f_i$，$ty=k-(a_{2,i}-y)\times f_i$。其中 $a_{1,i}$ 为 A 拥有的钞票 $i$ 的数量，$a_{2,i}$ 同理。$f_i$ 为第 $i$ 种钞票的面额。
然后转移方程就比较好想了。
我们知道，$dp_{i,tx,ty}$ 是**交换后**的，那么交换前的呢？就是 $dp_{i-1,j,k}$。
交换的代价？简单，把原钞票数量和枚举的 $x,y$ 一减，取个绝对值就完事了。
这看起来是对了。但是你手玩几个样例就会发现，这样算出来的代价刚好大了一倍。
为什么？因为这样算出来的是两人钞票的**变化次数**之和，但是题目让我们求的是**交换次数**。交换一次就是两人的钞票变化！
把代价除以 $2$ 即可。转移方程：
$$
dp_{i,tx,ty}\leftarrow \min\{dp_{i,tx,ty},dp_{i-1,j,k}+\frac{w}{2}\}
$$
设 $sx,sy$ 分别为 A、B 的目标金额。那么答案就为 $\min_{i=0}^6 dp_{i,sx,sy}$。特别地，如果答案为极大值，说明无解，输出 $\texttt{impossible}$。
时间复杂度 $\mathcal O(n^2)$，可以通过本题。
:::success[code]
```cpp line-numbers
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10,M=10;
const int inf=0x3f3f3f3f3f3f3f3f;
int xx,yy,zz;
int ans=inf;
int f[]={0,100,50,20,10,5,1};
int cnt[N],sum[N];
int a[4][N];
int dp[M][N][N];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>xx>>yy>>zz;
for(int i=1;i<=3;++i)
for(int j=1;j<=6;++j){
cin>>a[i][j];
sum[i]+=a[i][j]*f[j];
cnt[j]+=a[i][j];
}
sum[0]=sum[1]+sum[2]+sum[3];
memset(dp,0x3f,sizeof dp);
dp[0][sum[1]][sum[2]]=0;
for(int i=1;i<=6;++i){
for(int j=0;j<=sum[0];++j){
for(int k=0;k<=sum[0];++k){
if(j+k>sum[0]||dp[i-1][j][k]==inf) continue;
for(int x=0;x<=cnt[i];++x){
for(int y=0;y<=cnt[i];++y){
if(x+y>cnt[i]) continue;
int z=cnt[i]-x-y;
int tx=j-(a[1][i]-x)*f[i];
int ty=k-(a[2][i]-y)*f[i];
if(!(tx>=0&&ty>=0&&tx+ty<=sum[0])) continue;
int w=abs(a[1][i]-x)+abs(a[2][i]-y)+abs(a[3][i]-z);
dp[i][tx][ty]=min(dp[i][tx][ty],dp[i-1][j][k]+w/2);
}
}
}
}
}
int sx=sum[1]-xx+zz;
int sy=sum[2]-yy+xx;
int sz=sum[3]-zz+yy;
if(sx<0||sy<0||sz<0||sx+sy+sz!=sum[0]){
cout<<"impossible";
return 0;
}
for(int i=0;i<=6;++i)
ans=min(ans,dp[i][sx][sy]);
if(ans==inf) cout<<"impossible";
else cout<<ans;
return 0;
}
```
:::