如此可爱的动态规划见过么？

　　相信各位都非常喜欢动态规划，那我就写一道可爱的动态规划的题解吧。

题目：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，你在逗我。。。

精华：

　　多分析，可尝试动态规划多次：像本题一次区间规划，一次线性规划。

我们是：OIer~，我们要：Ac~，我们需：加油~~~！！！

巴特西

洛谷P5774，可爱的动态规划。

如此可爱的动态规划见过么？

题目：https://www.luogu.com.cn/problem/P5774

题意：

分析：

代码：

槽点：

精华：

我们是：OIer~，我们要：Ac~，我们需：加油~~~！！！

最新文章

热门文章

巴特西

洛谷P5774，可爱的动态规划。

如此可爱的动态规划见过么？

题目：https://www.luogu.com.cn/problem/P5774

题意：

分析：

代码：

槽点：

精华：

我们是：OIer~~~，我们要：Ac~~~，我们需：加油~~~！！！

最新文章

热门文章

我们是：OIer~，我们要：Ac~，我们需：加油~~~！！！