G Fascination Street
参考
给出一串n(2e5)个灯, 每个灯点亮可以照到相邻三个位置, 每个灯点亮都有不同的花费, 现在可以交换k(9)次灯的位置, 求把所有n个位置都照到的最小花费.
交换的肯定是一个亮的灯和一个灭的灯, 不然是没有意义的.(即, 将一个花费低的灯点亮, 根花费高, 未点亮的灯交换位置.)
对于每个位置i, 保存最后两个灯(i-1,i)是否点亮(注意是点亮, 不是被照到), 并保存当前有多少个点亮的灯被交换走, 多少个未点亮的灯被交换进来.
那么只会有4种转移方式:
点亮 花了钱, 灯到账
未点亮 没花钱, 不点亮
点亮被换走(对于这个位置相当于没电亮(因为换过来的是没点亮的)) 花了钱, 跑了
没点亮换过来一个(白piao) 没花钱, 到了
int n, k;
ll w[M];
ll dp[M][2][2][10][10];
// i a b x y
// 到i位置, i-1位置是a状态, i位置是b状态, 换走了a个点亮的, 换来了b个不亮的
void init() {
n = read(), k = read();
for (int i = 1; i <= n; i++)w[i] = read();
memset(dp, 0x3f, sizeof(dp));
dp[0][1][0][0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int x = 0; x <= 1; ++x) {
for (int y = 0; y <= 1; ++y) {
for (int a = 0; a <= k; a++) {
for (int b = 0; b <= k; ++b) {//点亮i+1
checkMin(dp[i + 1][y][1][a][b], dp[i][x][y][a][b] + w[i + 1]);
if (x || y)//不点亮i+1 不能有000
checkMin(dp[i + 1][y][0][a][b], dp[i][x][y][a][b]);
if (b < k)//别地方拿一个点亮的放在i+1 (相当于白嫖到一个点亮的)
checkMin(dp[i + 1][y][1][a][b + 1], dp[i][x][y][a][b]);
if (a < k && (x || y))//这个点亮之后, 放到其他位置去 (相当于没点亮)
checkMin(dp[i + 1][y][0][a + 1][b], dp[i][x][y][a][b] + w[i + 1]);
}
}
}
}
}
ll ans = INF;
for (int kk = 0; kk <= k; kk++) {
for (int x = 0; x <= 1; ++x) {
for (int y = 0; y <= 1; ++y) {
if (x || y)
checkMin(ans, dp[n][x][y][kk][kk]);
}
}
}
write(ans), enter;
}
I Game on Plane
咕