AcWing 300. 任务安排1（前缀和 dp优化）

菱形继承

于 2021-10-07 13:44:45 发布

阅读量230

点赞数

分类专栏： # Acwing 算法提高课文章标签：动态规划 c++

如果想转请私信博主，未经同意禁止转载~

本文链接：https://blog.csdn.net/weixin_43798170/article/details/120635322

版权

Acwing 算法提高课专栏收录该内容

41 篇文章

订阅专栏

在这里插入图片描述

思路：

在这里插入图片描述

代码：

#include<iostream>
#include<limits.h>
#include<cstring>
#define int long long
using namespace std;
const int N=5010;
int n,f[N],sumt[N],sumc[N],s;
//f[i][j]=f[k][j-1]+(t[1]+...+t[i]+j*s)*(c[k+1]+...+c[i])
signed main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        int t,c;
        cin>>t>>c;
        sumt[i]=sumt[i-1]+t;
        sumc[i]=sumc[i-1]+c;
    }
    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[j]+sumt[i]*(sumc[i]-sumc[j])+s*(sumc[n]-sumc[j]),f[i]);
        }
    }
    cout<<f[n]<<endl;
}