P5774题解
山田リョウ
·
·
题解
题目链接
u1s1 我认为这题怎么说也得蓝吧，不可能才绿。
这道题我们需要两次 dp。
第一次的 dp 数组我们叫做 g 数组吧，g_{i,j} 表示从第 i 号村庄出发，到第 j 号村庄，再回到第 i 号村庄治愈完 [i,j] 区间内所有的村庄时这 j-i+1 个村庄死的人数。
可以写出状态转移方程：
g_{i,j}=g_{i+1,j}+\min(\sum\limits_{k=i+1}^{j}a[k],3\times(j-i)\times a_i)
其中 3\times(j-i)，因为从 i+1 走到 j 再回到 i+1 需要 2\times(j-i) 的时间，但是治愈 i+1 到 j 这 j-i 个村庄还需要 j-i 的时间，所以总共需要 3\times(j-i) 的时间。
而 \sum\limits_{k=i+1}^{j}a[k] 这部分可以用前缀和优化一下。
这部分代码：
for(int i=n;i;--i)
for(int j=i+1;j<=n;++j)
g[i][j]=g[i+1][j]+sum[j]-sum[i]+min(3*(j-i)*(sum[i]-sum[i-1]),sum[j]-sum[i]);
第二次的 dp 数组我们就叫做 dp 吧，dp_i 指治愈 1 到 i 这 i 个村庄，而且最终回到 i 的最小死亡人数（这里要算上所有村庄）。
容易写出状态转移方程：
dp_i=\min\limits_{1\leq j<i}\{dp_j+g_{j+1,i}+(4\times i-4\times j-2)\times\sum\limits_{k=i+1}^n\}
$$(i-j)+[i-(j+1)]\times 2+[i-(j+1)+1]=4\times i-4\times j-2$$
而 $\sum\limits_{k=i+1}^n$ 同样可以用前缀和优化。
这一部分的代码：
```cpp
for(int i=1;i<=n;++i){
dp[i]=0x7fffffffffffffffll;
for(int j=0;j<i;++j)
dp[i]=min(dp[i],dp[j]+g[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i]));
}
```
这么做的复杂度是 $O(n^2)$ ，足以通过此题，全部代码如下：
```cpp
#include<stdio.h>
typedef long long ll;
inline ll min(ll a,ll b){return a<b?a:b;}
ll g[3001][3001],dp[3001],sum[3001];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){int x;scanf("%d",&x);sum[i]=sum[i-1]+x;}
for(int i=n;i;--i)for(int j=i+1;j<=n;++j)g[i][j]=g[i+1][j]+sum[j]-sum[i]+min(3*(j-i)*(sum[i]-sum[i-1]),sum[j]-sum[i]);
for(int i=1;i<=n;++i){dp[i]=0x7fffffffffffffffll;for(int j=0;j<i;++j)dp[i]=min(dp[i],dp[j]+g[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i]));}
printf("%lld",dp[n]);
return 0;
}
```