题目描述
有N个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。
机器会把这 N个任务分成若干批，每一批包含连续的若干个任务。
从时刻0开始，任务被分批加工，执行第 i个任务所需的时间是Ti。
另外，在每批任务开始前，机器需要S的启动时间，故执行一批任务所需的时间是启动时间 S加上每个任务所需时间之和。
一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。
也就是说，同一批任务将在同一时刻完成。
每个任务的费用是它的完成时刻乘以一个费用系数 Ci。
请为机器规划一个分组方案，使得总费用最小。
输入格式
第一行包含整数 N。
第二行包含整数 S。
接下来N行每行有一对整数，分别为Ti和 Ci，表示第 i 个任务单独完成所需的时间Ti及其费用系数 Ci。
输出格式
输出一个整数，表示最小总费用。
数据范围
1≤N≤5000,
0≤S≤50,
1≤Ti,Ci≤100
解题注意
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;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103280.html
