• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

luogu P5774 [JSOI2016]病毒感染 线性 dp

开发技术 开发技术 2周前 (05-12) 19次浏览

太难了,参考题解:https://www.luogu.com.cn/blog/An-Fly/soluti-p5774

#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]<<endl; return 0; } 

luogu P5774 [JSOI2016]病毒感染 线性 dp

原文地址:https://www.cnblogs.com/QingyuYYYYY/p/12875364.html


喜欢 (0)