有n?个村庄，每个村庄每天会因传染病去世ai个人(除非你治愈这个村庄)。
从1号村庄出发，每天可以选择向相邻的村庄进发或者治愈所在的村庄。
如果在这个过程中之前有未治愈的村庄，同时你往回走了一步，那么你需要把之前未治愈的村庄全部治愈后才能接着自由行动。
求所有村庄都被治愈时最少的死亡人数。
n≤3000,ai≤109
6
40 200 1 300 2 10
1950
见链接ヾ(。￣□￣)?゜゜゜
建议改成：江 苏 题 N B
暴力枚举n3显然不怎么优秀，所以我们选择动态规划。
转移方程：
dp[j][i+j]=dp[j+1][i+j]+min((sum[i+j]-sum[j])*2,a[j]*i*3+sum[i+j]-sum[j]);
dp2[i]=min(dp2[i],dp2[j]+dp[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i]));
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=3000+10; 5 ll n,dp[maxn][maxn],dp2[maxn],sum[maxn],a[maxn]; 6 7 int main(){ 8 scanf("%lld",&n); 9 for(ll i=1;i<=n;++i){ 10 scanf("%lld",&a[i]); 11 sum[i]=sum[i-1]+a[i]; 12 } 13 14 for(ll i=1;i<=n-1;++i) 15 for(ll j=1;j<=n-i;++j) 16 dp[j][i+j]=dp[j+1][i+j]+min((sum[i+j]-sum[j])*2,a[j]*i*3+sum[i+j]-sum[j]); 17 18 memset(dp2,0x3f,sizeof dp2); 19 dp2[0]=0; 20 for(ll i=1;i<=n;++i) 21 for(ll j=0;j<i;++j) 22 dp2[i]=min(dp2[i],dp2[j]+dp[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i])); 23 24 printf("%lld",dp2[n]); 25 return 0; 26 }
原文：https://www.cnblogs.com/Midoria7/p/12632886.html
