题目描述
有$N$个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。
机器会把这 $N$ 个任务分成若干批,每一批包含连续的若干个任务。
从时刻$0$开始,任务被分批加工,执行第 $i $个任务所需的时间是$T_i$。
另外,在每批任务开始前,机器需要$S$ 的启动时间,故执行一批任务所需的时间是启动时间 $S$ 加上每个任务所需时间之和。
一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。
也就是说,同一批任务将在同一时刻完成。
每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。
请为机器规划一个分组方案,使得总费用最小。
输入格式
第一行包含整数 $N$。
第二行包含整数 $S$。
接下来N行每行有一对整数,分别为$ Ti$ 和 $Ci$,表示第 $i$ 个任务单独完成所需的时间$T_i$及其费用系数 $C_i$。
输出格式
输出一个整数,表示最小总费用。
数据范围
$1≤N≤5000$,
$0≤S≤50$,
$1≤T_i,C_i≤100$
暴力枚举MLE——空间复杂度$O(n^2)$、时间复杂度$O(n^3)$
状态表示:①集合:$f[i][j]$表示前$i$个任务分成$j$组的集合。②属性:最小费用
状态计算:$f[i][j]=min(f[k][j-1]+(j×s+\sum_{a=1}^i t[i])×(\sum_{a=k+1}^i c[i]))$, $j-1≤k≤i$
最后一个不同点:最后一组,枚举最后一组的起点:可以分为前$k$个机器分为$j-1$组,$k+1$~$i$个机器是第$j$组
$\sum_{a=1}^i t[i]$和$\sum_{a=k+1}^i c[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;
}
感谢大佬, 费用提前解释得太好了
k不能等于i吧
暴力代码的 for(int k=j-1;k<=i;k++) 的 k可以=i吗?
应该不是j组集合把,j的作用应该是确定最后一组的位置把j+1~i。
$memset(f,0x3f3f3f3f,sizeof f);$ 不会爆吗
暴力枚举MLE——空间复杂度$O(n^2)$、时间复杂度$O(n^3)$,上面提到了会MLE
写得好啊