题目链接
题目大意：医疗团队来到n个村庄，n个村庄依次标号为1,2,…n。第i个村庄有ai个感染者。从1出发，每天可以去相邻村庄/治愈所在村庄，如果第i个村庄没有被治疗，那么每天这个村庄会死去ai个人,医疗团队在经过村庄i时，可能选择不治疗这个村庄而前往下一个村庄i+1,但是下次返回需要治疗之前所有未治疗的村庄，求最小死亡人数
题解：g[i][j]表示从j开始走，走到i，然后回头到j，i到j之间的村子的最小死亡人数,g[i][i]=0,考虑j这个村子一开始是治疗还是被跳过,跳过的话路程消耗3∗(i−j)天，每天村庄j死亡a[j]的人，治疗的话消耗1天，死亡sum[j+1,i]的人
g[i][j]=g[i][j+1]+sum[j+1,i]+min((i−j)∗3∗a[j],sum[j+1,i])
f[i]表示走到i，且前面的都治好了的情况下，总共的最小死亡人数
枚举j，考虑从j+1出发到i，然后回头到j+1，再回头到i，路途共消耗3∗(i−(j+1))天，治疗消耗(i−j+1)天，共4∗(i−j)−2天，每天死亡sum[i+1,n]的人
f[i]=min(f[j]+g[i][j+1]+sum[i+1,n]∗((i−j)∗4−2))
我的收获：真–脑洞……辅助dp……挺常用的……
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define ll long long const int M=3005; int n,a[M]; ll s[M],g[M][M],f[M]; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline ll sum(int l,int r){return s[r]-s[l-1];} void pre() { for(int i=1;i<=n;i++){ g[i][i]=0; for(int j=i-1;j>=1;j--) g[i][j]=g[i][j+1]+sum(j+1,i)+min(3ll*(i-j)*a[j],sum(j+1,i)); } } void work() { memset(f,0x3f,sizeof(f));f[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) f[i]=min(f[i],f[j]+g[i][j+1]+sum(i+1,n)*(4ll*(i-j)-2)); printf("%lld\n",f[n]); } void init() { n=read(); for(int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i]; pre(); } int main() { init(); work(); return 0; }