NC20231. [JSOI2016]病毒感染
描述
输入描述
输入第一行包含一个正整数 N。接下来一行包含 N 个整数，分别为a1,a2,.....,an。
输出描述
输出一行一个整数，表示最优行程安排下会死去的村民数量。
示例1
输入:
6 40 200 1 300 2 10
输出:
1950
C++ 解法, 执行用时: 136ms, 内存消耗: 46676K, 提交时间: 2022-01-29 15:17:31
#include<bits/stdc++.h>
using namespace std;
long long n,i,j,a[3002],s[3002],d[3002][3002],f[3002];
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i],s[i]=s[i-1]+a[i];
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
d[j][i+j]=d[j+1][i+j]+min((s[i+j]-s[j])*2,i*a[j]*3+s[i+j]-s[j]);
memset(f,0x7f,sizeof f);
f[0]=0;
for(i=1;i<=n;i++)
for(j=0;j<i;j++)
f[i]=min(f[i],f[j]+d[j+1][i]+(i*4-j*4-2)*(s[n]-s[i]));
cout<<f[n];
}