这里分享一种简单的方法。

#include<bits/stdc++.h>
using namespace std;
const int N=7;
const int inf=0x3f3f3f3f;
const int w[7]={0,100,50,20,10,5,1};
int sa,sb,sc,a[N],b[N],c[N];
int dfs(int i,int A,int B,int C){
	if(A>sa||B>sb||C>sc)return inf;
	if(i==7)return 0;
	int res=inf,n=a[i]+b[i]+c[i];
	for(int j=0;j<=n;j++){
		for(int k=0;j+k<=n;k++){
			res=min(res,dfs(i+1,A+j*w[i],B+k*w[i],C+(n-j-k)*w[i])+abs(j-a[i])+abs(k-b[i])+abs(n-j-k-c[i]));
		}
	}
	return res;
}
int main(){
	int s1,s2,s3;scanf("%d%d%d",&s1,&s2,&s3);
	for(int i=1;i<=6;i++){
		scanf("%d",&a[i]);
		sa=sa+a[i]*w[i];
	}
	for(int i=1;i<=6;i++){
		scanf("%d",&b[i]);
		sb=sb+b[i]*w[i];
	}
	for(int i=1;i<=6;i++){
		scanf("%d",&c[i]);
		sc=sc+c[i]*w[i];
	}
	sa=sa-s1+s3,sb=sb-s2+s1,sc=sc-s3+s2;
	int ans=dfs(1,0,0,0);
	if(ans==inf)puts("impossible");
	else printf("%d",ans/2);
	return 0;
}

分析

看起来就很 DP。设 $f(i,j,k)$ 表示前 $i$ 种面值的钞票进行了一些交换，此时 Alice 有 $j$ 元钱，Bob 有 $k$ 元钱，最少的交换次数。

设刚开始三人分别有 $s_1,s_2,s_3$ 元钱，目标是三人分别有 $e_1,e_2,e_3$ 元钱。

初始状态 $f(0,s_1,s_2)=0$。枚举第 $i+1$ 种面值的钞票，Alice 和 Bob 各留下几张转移。

这样时间复杂度是 $O(6\times2000^2\times 30^2)$，过不了。

加两个优化：

1. 面值的考虑顺序是不影响结果的，先考虑面值较小的，此时有值的状态不会很多，再考虑面值较大的，这样的钞票数量不会很多，比较优。记忆化搜索。
2. 从小到大考虑时，如果剩下的面值的 $\gcd$ 不整除 $j-e_1$ 或者 $k-e_2$ 那就无解。

这时候跑得就比较快了，能够稳定跑进 200ms。

实现

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 4, M = 7, K = 2005, val[M] = {0, 1, 5, 10, 20, 50, 100},
          d[M] = {1, 5, 10, 10, 50, 100}, INF = 0x3f3f3f3f;
int f[M][K][K], x[N], s[N], e[N], num[N][M], tot[M], n;

int calc(int i, int j, int k) {
  return (abs(j - num[1][i]) + abs(k - num[2][i]) +
          abs(tot[i] - j - k - num[3][i])) >>
         1;
}

int F(int i, int j, int k) {
  if (i == M - 1) return j == e[1] && k == e[2] ? 0 : INF;
  if ((e[1] - j) % d[i] || (e[2] - k) % d[i]) return INF;
  int J = j + n, K = k + n;
  if (f[i][J][K] != -1) return f[i][J][K];
  f[i][J][K] = INF;
  for (int x = 0; x <= tot[i + 1]; x++)
    for (int y = 0; x + y <= tot[i + 1]; y++)
      f[i][J][K] =
          min(f[i][J][K], F(i + 1, j + (x - num[1][i + 1]) * val[i + 1],
                            k + (y - num[2][i + 1]) * val[i + 1]) +
                              calc(i + 1, x, y));
  return f[i][J][K];
}

int main() {
  cin >> x[1] >> x[2] >> x[3];
  for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++) cin >> num[i][M - j];
  for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++) tot[j] += num[i][j], s[i] += num[i][j] * val[j];
  e[1] = s[1] + x[3] - x[1], e[2] = s[2] + x[1] - x[2],
  e[3] = s[3] + x[2] - x[3];
  if (e[1] < 0 || e[2] < 0 || e[3] < 0) return puts("impossible"), 0;
  memset(f, -1, sizeof(f)), n = s[1] + s[2] + s[3];
  int ans = F(0, s[1], s[2]);
  if (ans == INF) puts("impossible");
  if (ans != INF) cout << ans << endl;
  return 0;
}