任务安排 | Axell's Blog

题目链接

题目描述

思路

直接DP会产生后效性，可以把后面的任务因为本次任务产生的额外费用统计在本次任务中
状态转移方程为：
dp[i]=min(dp[i],dp[j]+(f[n]-f[i])*s「额外增加的费用」+(f[i]-f[j])*(t[i]+s))「本次前面一段的费用」
初始值: DP[0]=0 目标:DP[n]

代码

#include <bits/stdc++.h>
using namespace std;

int t[5005],f[5005],n,s;
long long dp[5005];
int main(){
    cin>>n>>s;
    for (int i=1;i<=n;++i) scanf("%d %d",&t[i],&f[i]),t[i]+=t[i-1],f[i]+=f[i-1];
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for (int i=1;i<=n;++i){
        for (int j=i-1;j>=0;--j){
            dp[i]=min(dp[i],dp[j]+(f[n]-f[i])*s+(f[i]-f[j])*(t[i]+s));
        }
    }
    printf("%lld\n",dp[n]);
    return 0;
}

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/80/