不带滚动数组代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int N = 2000010;
int a[N], c[N], T, n, f[N];
signed main() {
scanf("%lld", &T);
while (T -- ) {
memset(f, 0, sizeof f);
scanf("%lld", &n);
for (int i = 1; i <= n; i ++ )
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i ++ )
scanf("%lld", &c[i]);
int min0 = 1e10, min1 = 1e10;
for (int i = 1; i <= n; i ++ ) {
f[i] = f[i - 1] + a[i] + a[i]; // 只选择这一个打扫
if (c[i] == 0) f[i] = min(f[i], min0 + a[i]);
if (c[i] == 1) f[i] = min(f[i], min1 + a[i]);
if (c[i] == 0) min0 = min(min0, f[i - 1] + a[i]);
if (c[i] == 1) min1 = min(min1, f[i - 1] + a[i]);
}
printf("%lld\n", f[n]);
}
return 0;
}
带滚动数组代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int N = 2000010;
int a[N], c[N], T, n, f[2];
signed main() {
scanf("%lld", &T);
while (T -- ) {
f[0] = f[1] = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; i ++ )
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i ++ )
scanf("%lld", &c[i]);
int min0 = 1e10, min1 = 1e10;
int now = 1;
for (int i = 1; i <= n; i ++ ) {
f[now] = f[now ^ 1] + a[i] + a[i]; // 只选择这一个打扫
if (c[i] == 0) f[now] = min(f[now], min0 + a[i]);
if (c[i] == 1) f[now] = min(f[now], min1 + a[i]);
if (c[i] == 0) min0 = min(min0, f[now ^ 1] + a[i]);
if (c[i] == 1) min1 = min(min1, f[now ^ 1] + a[i]);
now ^= 1;
}
printf("%lld\n", f[now ^ 1]);
}
return 0;
}