我连题目都看不懂。。。


题意

有$n$个村庄按标号排列,每个村庄有一个死亡速度$a_i $,表示每天死$a_i $人(除非你治好这个村庄)。

你从$1 $号村庄出发,每天可以选择向相邻的村庄进发或者治愈所在的村庄。

如果在这个过程中你的左边有未治愈的村庄,同时你向左走了一步,那么你需要把这些村庄全部治愈后才能接着自由行动。

求所有村庄都被治愈时最少的死亡人数。

$n≤3000,a_i≤10^9$

题解

根据别人博客的题意,我成功理解了题意(雾

有一个很明显的结论:过程一定是多个折返叠加再一起的。

那么有主状态$f_i$,表示前$i$个村庄已全部被治愈,且现在在$i$。

那么有

$f_i=\min\limits_{j<i}\{f_j+[j\ne 0](s_n-s_j)+g_{j+1,i}+[i\ne n](i-j-1)(s_n-s_i)\}$

副状态$g_{i,j}$表示从$i\rightarrow j\rightarrow i$的最小费用。

枚举$i$是返回后才治愈,还是返回前就治愈,有

$g_{i,j}=g_{i+1,j}+\min\{3a_i(i-j)+(s_n-s_i)+2(s_n-s_j),2(s_n-s_i)+(s_n-s_j)\}$

也就是在$i+1$的状态下,多考虑了从$i\rightarrow i+1,i+1\rightarrow i$的转移。

其实可以发现$f_i$的转移有些状态看上去不怎么合理,但最优解的转移一定包含在所有的转移里面。

这个很容易证明决策包含性。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
using namespace std;
const int N=3005,mod=1e9+7;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[N],g[N][N],s[N];int a[N]; 
int main()
{
    memset(f,0x3f,sizeof(f));
    int n;qr(n);f[0]=0;
    for(int i=1;i<=n;i++)qr(a[i]),s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)g[i][i]=s[n]-s[i];
    for(int j=2;j<=n;j++)
        for(int i=j-1;i;i--)
            g[i][j]=g[i+1][j]+min(3ll*a[i]*(j-i)+s[n]-s[i]+2*(s[n]-s[j]),2*(s[n]-s[i])+s[n]-s[j]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+(j!=0)*(s[n]-s[j])+g[j+1][i]+(i!=n)*(i-j-1)*(s[n]-s[i]));
    qw(f[n]);puts("");
    return 0;
}