[bzoj 1021] [SHOI2008]Debt 循环的债务

A, B, C之间相互欠钱. 每个人有一些面额100,50,20,10,5,1元的钞票. 求三人还清债务需要交换钞票的最少张数, 或报告不能还清. (每人拥有的10,5,1元钞票张数不超过30, 三人总共拥有的钞票面值总额不超过1000, 任何一个人欠另一个人的钱数的绝对值不超过1000) 做完这道题之后, 我有点生气......生自己的气......TAT

分明是个很裸的DP, 然而我的注意力被换零钱可以贪心吸引了, 并想到枚举的方向去了......但是得枚举4个量, 超时......

设f[i][j][k]表示前i种面额的钞票, 从初始状态到A有j元, B有k元, 最小交换张数. 共有6种转移.

template<typename T>
inline void upmin(T& x, T v)
{
	x = min(x, v);
}

const int v[] = {100, 50, 20, 10, 5, 1}, N = 1e3 + 1, inf = 0x3f3f3f3f;
int A[6], B[6], C[6], f[2][N][N];

int main()
{
	int x1, x2, x3, a = 0, b = 0, c = 0;
	scanf("%d%d%d", &x1, &x2, &x3);
	rep (i, 0, 6) scanf("%d", A+i), a += v[i] * A[i];
	rep (i, 0, 6) scanf("%d", B+i), b += v[i] * B[i];
	rep (i, 0, 6) scanf("%d", C+i), c += v[i] * C[i];
	int s = a + b + c;
	
	memset(f[1], 0x3f, sizeof f[1]);
	f[1][a][b] = 0;
	
	rep (i, 0, 6) {
		int (*g)[N] = f[(i & 1)^1], (*h)[N] = f[i & 1];
		memset(h, 0x3f, sizeof f[i & 1]);
		
		rep (x, 0, s+1) rep (y, 0, s-x+1) {
			int z = s-x-y, t = g[x][y];

			if (t == inf) continue;
			
			rep (j, 0, A[i]+1) rep (k, 0, A[i]-j+1)
				if (x >= (j+k) * v[i])
					upmin(h[x - (j+k)*v[i]][y + j*v[i]], t + j + k);

			rep (j, 0, B[i]+1) rep (k, 0, B[i]-j+1)
				if (y >= (j+k) * v[i])
					upmin(h[x + j*v[i]][y - (j+k)*v[i]], t + j + k);

			rep (j, 0, C[i]+1) rep (k, 0, C[i]-j+1)
				if (z >= (j+k) * v[i])
					upmin(h[x + j*v[i]][y + k*v[i]], t + j + k);

			int p = min(A[i], x/v[i]), q = min(B[i], y/v[i]), r = min(C[i], z/v[i]);
			
			rep (j, 0, p+1) rep (k, 0, q+1)
				upmin(h[x - j*v[i]][y - k*v[i]], t + j + k);

			rep (j, 0, p+1) rep (k, 0, r+1) 
				upmin(h[x - j*v[i]][y + (j+k)*v[i]], t + j + k);
			
			rep (j, 0, q+1) rep (k, 0, r+1)
				upmin(h[x + (j+k)*v[i]][y - j*v[i]], t + j + k);
		}
	}

	a = a - x1 + x3;
	b = b - x2 + x1;
	c = c - x3 + x2;
	
	if (a < 0 || b < 0 || c < 0 || f[1][a][b] == inf) puts("impossible");
	else printf("%d\n", f[1][a][b]);

	return 0;
}