自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:49:05，当前版本为作者最后更新于2021-12-14 10:10:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

*P3448 [POI2006]MIS-Teddies

POI 合集。

还算有趣的 DP，感觉难度没有黑牌。

奇奇怪怪的限制 + 很小的数据范围，动态规划没跑了。注意到我们根本不需要知道序列长什么样，只要每种玩具放的个数以及最后两个玩具是什么就可以转移了。因此设六维 DP $f_{i,j,k,l,m,n}$ 表示放了 $i,j,k,l$ 个 $A1,A2,B1,B2$（分别标号为 $0,1,2,3$），最后两个玩具分别是 $m$ 和 $n$ 的方案数，转移直接枚举下一个放什么，检查一下是否符合题意即可。

空间复杂度可以通过滚动数组优化。时间复杂度四方，有 $64$ 倍常数。

const int N = 39;
const int mod = 1e6;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int a, b, c, d, ans, f[2][N][N][N][4][4];
bool check(int x, int y, int z) {
	if(x == -1) return 1;
	int a = (x & 1) + (y & 1) + (z & 1), b = (x < 2) + (y < 2) + (z < 2);
	return a && a < 3 && b && b < 3;
}
int main(){
	cin >> a >> b >> c >> d, f[0][0][0][0][0][0] = 1;
	for(int I = 0, i = 0; I <= a; I++, i ^= 1) {
		mem(f[i ^ 1], 0, N);
		for(int j = 0; j <= b; j++)
			for(int k = 0; k <= c; k++)
				for(int l = 0, s = I + j + k; l <= d; l++, s++)
					for(int x = 0; x < 4; x++)
						for(int y = 0, v; y < 4; y++)
							if(v = f[i][j][k][l][x][y]) {
								int q2 = s <= 1 ? -1 : x, q1 = !s ? -1 : y;
								if(I < a && check(q2, q1, 0)) add(f[i ^ 1][j][k][l][y][0], v);
								if(j < b && check(q2, q1, 1)) add(f[i][j + 1][k][l][y][1], v);
								if(k < c && check(q2, q1, 2)) add(f[i][j][k + 1][l][y][2], v);
								if(l < d && check(q2, q1, 3)) add(f[i][j][k][l + 1][y][3], v);
							}
	}
	for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) add(ans, f[a & 1][b][c][d][i][j]);
	cout << ans << endl;
	return 0;
}