如此可爱的动态规划见过么？
相信各位都非常喜欢动态规划，那我就写一道可爱的动态规划的题解吧。
题目：https://www.luogu.com.cn/problem/P5774
题意：
题意“挺明白”的。。。题意：给你一个序列每个数表示第i个村庄一天要因感染而死的人数，大佬你能治这种病，花费一天治好一个村庄，而你移动还要花费一天，问治愈好所有村庄最少死的人。限制：只要从i走到i-1，就必须把i之前的所有村庄全部治愈。
分析：
这题很容易看出是动态规划，但是，怎么规划呢（要求时间效率n方），暴力规划n，我们并不能很好的解决它，那咋办：单调队列？？，好像没啥单调。。。我们只能想别的办法：二分答案？？，好像也不是很好判断死多少人可以完成，还是要回到动态规划。
枚举长度，起点，断点三个是不行的，那我们可不可考虑先维护2个？
我们先枚举起点和长度：那我们怎么做才能不用枚举断点呢？——加限制：我们定义Dp[i][j]表示治愈好i到j所有人过程中i到j中的死亡的最少人数,并且要求路线是i到j到i，于是，我们就可不枚举断点了，为什么呢：想一想，我们限制路线之后，Dp[i][j]的转移就不由得你去枚举断点了
然后想出转移方程（这个就推导一下就好了，关键是怎么n变n）
Dp[i][j]=Dp[i+1][j]+min((sum[j]-sum[i])*2,a[i]*(d-1)*3+sum[j]-sum[i]);
可是显然Dp[i][n]并不是我们最后想要的结果，因为我们并不一定要1到n到1，中间可以回头。
不过没关系，我们已经成功一半了，我们再定义一个数组dp[i]表示前i个村庄被治愈之后，1到n总共最少死的人数，你会发现：不用枚举起点，太棒了，只要想出转移方程来就可以了：
dp[i]=min(dp[j]+Dp[j+1][i]+(4*(i-j)-2)*(sum[n]-sum[i]))（j属于n，j<i）
最后，显然Dp[n]就是我们想要的答案了。
很可爱的动态规划，大家是不是更爱动态规划了呢？
代码：
又是极度的简单
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int maxn=+;
long long a[maxn],sum[maxn],Dp[maxn][maxn],dp[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
sum[i]=sum[i-]+a[i];
}
for(int d=;d<=n;d++)
for(int i=,j;(j=i+d-)<=n;i++)
Dp[i][j]=Dp[i+][j]+min((sum[j]-sum[i])*(long long),a[i]*(long long)(d-)*(long long)+sum[j]-sum[i]);
memset(dp,0x3f,sizeof(dp));
dp[]=;
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
dp[i]=min(dp[i],dp[j]+Dp[j+][i]+((long long)*(long long)(i-j)-(long long))*(sum[n]-sum[i]));
printf("%lld",dp[n]);
return ;
}
没注释，各位大佬应该一看就懂
槽点：
死亡人数用long long，你在逗我。。。
精华：
多分析，可尝试动态规划多次：像本题一次区间规划，一次线性规划。