任务安排1

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

思路：首先可以想到dp[i][j]表示i个任务分成j次完成。这样状态转移方程就是dp[i][j]=min(dp[k][j-1]+(m*j+a[i])*(b[i]-b[k])；k是用从0循环到j。

但这样的时间复杂度是O(n³)，肯定会超时的。换一种方法，我们可以知道，机器因执行这批任务而花费的启动时间s，会累加到在此之后所有任务的完成时刻上。

设dp[i[表示把前i个任务分成若干批执行的最小费用。所以转移方程为：dp[i]=min(dp[i],dp[j]+a[i]*(b[i]-b[j])+m*(b[n]-b[j]));

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
#define INF 0x7ffffff
ll dp[5010],a[5010],b[5010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i]=a[i-1]+x;
        b[i]=b[i-1]+y;
    }
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
        dp[i]=min(dp[i],dp[j]+a[i]*(b[i]-b[j])+m*(b[n]-b[j]));
    cout<<dp[n]<<endl;
}