跳到主要内容

斜率优化DP

AcWing 300. 任务安排1​

题目链接：https://www.acwing.com/problem/content/302/

思路​

状态表示：f[i]表示所有将前i个方案处理完的所有方案的集合的最小值

状态转移方程：f[i]=min(f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j])) 其中0<j<i0<j<i

c[i]和t[i]是前缀和

代码​

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
typedef long long LL;

const int N=5010;
LL t[N],c[N],n,s,f[N];

int main()
{
    memset(f,0x3f,sizeof f);
    f[0]=0;
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>t[i]>>c[i];
    for(int i=1;i<=n;i++) t[i]+=t[i-1],c[i]+=c[i-1];

    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+t[i]*(c[i]-c[j])+s*(c[n]-c[j]));
    cout<<f[n];
    return 0;
}
0%