大致题意
有(N)个小镇爆发了疫情,其中第(i)个小镇每天会死(a_i)个人,现在从第一个小镇出发,每一天可以选择:
-
走向一个相邻的村庄,若往左走,则必须把之前所有未治愈村庄全部治愈
-
治疗目前所在的村庄,这一天内该村庄内不会有任何人死去
求最少死亡人数
(n≤3000,a_i≤10^9)
分析
可以发现,每个村庄只可能在第一次被经过或第二次被经过时治愈被治愈,换句话说,在区间([l,r])进行一次往返走((l Rightarrow r Rightarrow l Rightarrow r))可以治愈该区间内的所有村庄,并且总过程就是由一连串的"往返走"组成的
不妨先设(f(i))表示治疗前(i)个村庄的最少死亡人数,(v(i,j))表示在区间([l,r])进行一次往返走后该区间的最少死亡人数,转移也比较好推,就是细节比较多:
显然这个(v(i,j))也是可以用(DP)预处理出来的,分类讨论治愈的时间,有转移:
时间复杂度(O(n^2))
(code)
//xcxc82 2021/1/19/22:03
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3010;
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;return ~(X-1);
}
int n,a[MAXN];
int v[MAXN][MAXN],sum[MAXN];
int f[MAXN];
signed main(){
n =read();
for(int i=1;i<=n;i++) a[i] = read(),sum[i] = sum[i-1]+a[i];
memset(f,0x3f,sizeof(f));
memset(v,0x3f,sizeof(v));
f[0]=0;
for(int i=1;i<=n;i++){
v[i][i] = 0;
}
for(int len=1;len<=n-1;len++){
for(int i=1;i+len<=n;i++){
int j=i+len;
v[i][j] = v[i+1][j]+min(2*(sum[j]-sum[i]),a[i]*3*len+sum[j]-sum[i]);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
f[i] = min(f[j]+v[j+1][i]+(4*(i-j)-2)*(sum[n]-sum[i]),f[i]);
}
}
printf("%lld",f[n]);
return 0;
}