解题注意 1、

dp数组含义的定义问题

c[n]−c[j])×s

c[n]-c[i]+c[i]-c[j]

需要考虑c[n]-c[i]的影响（不是j循环的影响，而是每一个i分组后就会产生这样的影响）

2、

完成时刻的问题

错误尝试：用数组记录每一个任务的完成时刻（错误f[n]定义下的错误思路）

当使用新f[n]定义时，数组记录的s就被封装在f[n]里，那记录时间的数组就没必要了。

不用记录，是可以封装的（封装在f[n]里面）

3、

注意：这题用基本的方法不能用一维的dp，因为题目的特性决定的。

要用一维的dp需要重新定义dp数组含义。

暴力枚举MLE——空间复杂度O(n2)、时间复杂度O(n3) 状态表示：

①集合:f[i][j]表示前i个任务分成j组的集合。

②属性:最小费用 状态计算：f[i][j]=min(f[k][j−1]+(j×s+∑(i)(a=1)t[i])×(∑(i)(a=k+1)c[i])), j−1≤k≤i 最后一个不同点：最后一组，枚举最后一组的起点：可以分为前k个机器分为j−1组，k+1~i个机器是第j组∑ia=1t[i]和∑ia=k+1c[i]

可以用前缀和优化

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5010;
int t[N],c[N];
int f[N][N];
int n,s;
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x3f3f3f3f,sizeof f);
    f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            for(int k=j-1;k<=i;k++)
                f[i][j]=min(f[i][j],f[k][j-1]+(j*s+t[i])*(c[i]-c[k]));
 
    int res=0x3f3f3f3f;
    for(int i=1;i<=n;i++) res=min(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}

为什么要写暴力?

所有题目拿下来都可以先向暴力的方向去想，然后再进行优化

进一步思考 我们为什么要枚举每一组？是为了得到启动机器的次数进而算费用 我们可以发现，只要我们分一组，后面还未分组的机器一定会增加相应的费用，高兴的是我们现在就可以算出来增加的费用是多少，所以我们只需要提前把这个多出来的费用加上就行了 状态转移方程：f[i]=min(f[j]+(c[i]−c[j])×t[i]+(c[n]−c[j])×s),0≤j<i 同上c[i]和t[i]是前缀和。

优化后

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5010;
int t[N],c[N];
int f[N];
int n,s;
int main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x3f3f3f3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)    
            f[i]=min(f[i],f[j]+(c[i]-c[j])*t[i]+(c[n]-c[j])*s);
    cout<<f[n]<<endl;
    return 0;
}

az

az

az