自动搬运

查看原文

来自洛谷，原作者为

	Su_Zipei 与卿再世相逢日,玉树临风一少年

搬运于2025-08-24 22:14:16，当前版本为作者最后更新于2020-04-14 07:55:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

_ _ _ _# 原题链接：https://www.luogu.com.cn/problem/P5774

分析

直接看这道题，第一个困惑点，那个绝对值的比较是什么东西，根据数学知识，我们可以知道这个意思是$k$到$i$的距离小于$k$到$j$的距离，而路线是线性的，这就意味着当且仅当$k$在$j$的左边时才成立，不然总会有$k-i>k-j$，还不理解？看下图 如果$K$在$K'$的位置，那么$K-i$一定大于$K-j$吧，所以这个题的题意是只要从$j$往回走去治愈$K$，就必须把之前没治愈过的村庄也治愈了。

想到这里，状态就差不多出来了，定义$DP_i$表示治愈前i个村庄的最小死亡数，下面考虑状态转移，对于$JYY$来说，每个村庄它都有两个选择，治愈$or$先去别的再走回来治愈，治愈的话很好弄，主要考虑的就是略过它的情况，这时候如果依次枚举$K$，效率应该是$N^3$，程序吃不消，$3000$的极限数据我们最少也要压到$N^2$左右，所以接下来考虑优化。

优化其实也挺简单的，主要有一点很恶心，下边再说。（从这里开始默认$j$在$i$的前边，请勿被上图迷惑）我们发现多出来的时间主要是用在了计算略过村庄再回来的死亡人数的计算，所以我们可以先考虑预处理出从$j$到$i$再从$i$到$j$然后又回到i这一过程中最少的死亡数，于是定义$g_{i,j}$含义为上述的来辅助我们的$DP$。我还是补一张图吧……把我自己绕懵了 看了这张图我相信你就明白了$g$数组的含义，接下来考虑如何求解$g$数组，初始的话$g[i][i]$肯定是为0的，所以转移都应该从这个位置开始，即倒序，那么怎么转移呢，接下来就是很恶心的一个地方，计算经过的天数！很多题解里都没写到这个，这里详细计算一下。

对于$g_{i,j}$，同样分两种情况讨论，救助或是略过，不管是救助还是略过，都避免不了经过一个区间，就是$j+1$到$i$，所以这里可以分而治之，把$j$和$j+1$到$i$这两个分开，$g_{i,j}$的转移中应该需要有$g_{i,j+1}$，这里又启示我们进行倒序循环，同样，不管救助$j$还是略过，从$j$走到$j+1$的这一天里，区间$j+1$到$i$这一段的村庄都会死亡（为村民默哀？）所以答案累加$Sum_{j+1,i}$这个可以由前缀和$O(1)$求出，到了点$j+1$后，$j+1$到$i$的死亡人数就已经被记在了$g_{i,j+1}$里，所以可以不用考虑，这是两种情况所共同具有的死亡人数，下面对两种情况分开讨论，如果救治$j$的人，那么区间$j+1$，$i$的村民就要多死一天，即$Sum_{j+1,i}$，不救治呢？因为同样的我们跑路的代价都记录在了$g_{i,j+1}$里边，所以不救治的代价就是在这段时间里$j$村死亡的人数，你可能问，别的村难道没有死亡的吗？当然可能会有，但我们已经记录了，所以这里不需要再次加入，首先算一下从$j$跑到$i$再跑回来所需要的时间，这里举个例子，从4到5要1天，4到6要2天，4到7要3天，所以显然跑路时$j$村死亡的人是$2*(i-j)*a_j$，2是跑了两遍，$i-j$是刚刚推出来的，$a_j$是$j$村日死亡人数，那只有这些吗？当然不是，这只是跑路的代价，根据定义和题意，$j+1$到$i$这些村庄均被治愈且均在略过$j$后被治愈，所以一个村庄一天，一共就是$(i-(j+1)+1)*a_j$天，于是我们的$g_{i,j}$就有了转移方程 $g_{i,j}$=$g_{i,j+1}$+$Sum_{j+1,i}$+$min$($3*(i-j)*a_j$，$Sum_{j+1,i}$)

辅助进行转移的方程有了之后我们就可以进行$dp$的转移了，没错，下边还有很恶心的算时间。

对于每前$i$个村庄，都不可能直接求出他的最小值，所以要枚举中间点$j$，即我治愈了前$j$个村庄，但是$j+1$被略过了，所以$j+1$的治愈是从$j+1$走到$i$再走回来时才被治愈，这一段的代价就是$g_{i,j+1}$，治愈前j个的代价为$dp_j$，直接累加答案即可，那么最硬核的东西就是$i+1$到$n$的这段区间，因为在当前阶段，这段区间内的人是不可能被治愈的，所以一天内的死亡人数是$Sum_{i+1,n}$，天数呢？根据我之前所推导的，从$j+1$到$i$之间反复横跳一来一回一来需要天数$3*(i-(j+1))$，治愈区间$j+1$到$i$需要时间$(i-(j+1)+1)$。

这里不要忽略了一个地方，就是从$j$跑路跑到$j+1$时还有一天，所以总天数就是$3*(i-(j+1))+i-(j+1)+1+1$，乘上每天死亡的人数就是最后的代价，累加答案。

至此，这道省选题就落下了帷幕……什么？你问我最后转移的时候没考虑略过$i$就是一路向右的情况？怎么可能，当我枚举到$j=i-1$的时候，就相当于转移了这种情况，是吧，所以这个算法是没有问题的，时间复杂度大致为$O(n^2)$可以A掉

$Tips$：：如果你实在看不懂时间怎么算的请拿起笔自己模拟一下吧，很快就能懂，我也尽力了。

#include<iostream>
#include<cstring>
#define ll long long 
using namespace std;
const int N=3e3+10;
ll s[N],g[N][N],dp[N],a[N];
ll Sum(int l,int r){
    return s[r]-s[l-1];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];a[i]=s[i];s[i]+=s[i-1];
    }
    for(int i=1;i<=n;i++)
    for(int j=i-1;j;j--)
        g[i][j]=g[i][j+1]+Sum(j+1,i)+min(3LL*(i-j)*a[j],Sum(j+1,i));
    memset(dp,0x3f,sizeof dp);
    dp[0]=0;
    for(int i=1;i<=n;i++)
    for(int j=0;j<i;j++)
        dp[i]=min(dp[i],dp[j]+g[i][j+1]+Sum(i+1,n)*((i-(j+1))*3+i-(j+1)+2));
    cout<<dp[n];
}