Petrozavodsk Summer-2014. Andrew Stankevich Contest 46. E.Ebola Virus
题目大意
在一条直线上有 $n$ 个村庄，每个村庄共有 $a_i$ 个病人，这些人每天会导致 $a_i$ 个同村庄中的未患病的人死亡。你初始时在 $1$ 号村庄，你可以选择花费一天走向相邻的村庄，或者治疗你所在的村庄中的所有病人。但是如果你决定往回走，那么你需要将所有你错过的村庄依次全部治疗。问最少死去的人数为多少。
题目分析
考虑使用 DP 来解决这道题。首先设 $g[l][r]$ 为从 $l$ 村庄走到 $r$ 村庄并治疗这些村庄中的所有人会导致这些天中 $l$ 到 $r$ 村庄死去的最少的人数。那么有两种可能，第一种是在 $l$ 村庄中治疗，随后再走向下一个村庄。那么这样会导致 $l$ 之后的所有村庄的人数死亡两次；第二种情况是先不治疗 $l$ 中的所有人，而是先治疗 $[l + 1, r]$ 的人。那么 $l$ 村庄的人们会死 $3 \cdot (r – l)$ 次，同时移动还造成了一次 $l$ 之后的所有村庄死一次人。
有了 $g$ 数组，考虑如何构造出整个答案。定义 $f[i]$ 为走到 $i + 1$ 村庄，治疗全部 $i$ 及之前的全部村庄造成全部村庄的最少死亡人数。那么对于任何一个 $i$，有两种可能情况，第一种可能是治疗第 $i$ 个村庄并走向下一个村庄，那么 $i$ 之后的所有村庄将全部死亡两次。还有一种可能，是先走到 $j$ 村庄，不治疗 $j$ 村庄，并向后走，走到 $i$ 并返回 $j$ 随后再走向 $i + 1$ 村庄。那么除了 $g[i][j]$ 的死亡， $i$ 之后的村庄总共死了 $4 \cdot (i – j)$ 次用在经过和治疗 $[l, r]$ 的村庄，同时还有治疗 $i$ 和走向 $i + 1$ 村庄的花费，也就是 $4 \cdot (i – j) + 2$ 次。取一下最小值即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 3005;
long long inf = 0x3f3f3f3f3f3f3f3f;
int n;
long long a[maxn];
long long f[maxn];
long long sum[maxn];
long long g[maxn][maxn];
int main(){
long long i, j;
long long tmp;
long long c;
while(~scanf("%d", &n) and n){
memset(a, 0, sizeof(a));
memset(sum, 0, sizeof(sum));
for(i=1;i<=n;i++){
scanf("%lld", &a[i]);
}
for(i=1;i<=n;i++){
sum[i] = sum[i - 1] + a[i];
g[i][i] = 0;
}
for(i=n;i>0;i--){
for(j=i+1;j<=n;j++){
g[i][j] = g[i + 1][j] + min((sum[j] - sum[i]) * 2ll, a[i] * (j - i) * 3ll + sum[j] - sum[i]);
}
}
f[0] = 0;
for(i=1;i<=n;i++){
f[i] = f[i - 1] + 2ll * (sum[n] - sum[i]);
for(j=i-1;j>0;j--){
f[i] = min(f[i], f[j - 1] + g[j][i] + (4 * (i - j) + 2) * (sum[n] - sum[i]));
}
}
printf("%lld\n", f[n]);
}
return 0;
}