1197 -- 【算法竞赛】任务安排
Description
有N个任务排成一个序列在一台机器上等待执行,它们的顺序不得改变。机器会把这N个任务分成若干批,每一批包含连续的若干个任务。从时刻0开始,任务被分批加工,执行第 i 个任务所需的时间是 Ti。另外,在每批任务开始前,机器需要S的启动时间,故执行一批任务所需的时间是启动时间S加上每个任务所需时间之和。
一个任务执行后,将在机器中稍作等待,直至该批任务全部执行完毕。也就是说,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci。请为机器规划一个分组方案,使得总费用最小。
例如：S=1；T={1,3,4,2,1}；C={3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5},则完成时间分别为{5,5,10,14,14},费用 {15,10,30,42,56},总费用就是153。
Input
第一行是N(1<=N<=5000)。
第二行是S(0<=S<=50)。
下面N行每行有一对数,分别为Ti和Ci,均为不大于100的正整数,表示第i个任务单独完成所需的时间是Ti及其费用系数Ci。
Output
输出仅一个整数,表示最小的总费用。
Sample Input
5 1 1 3 3 2 4 3 2 3 1 4
Sample Output
153
Hint
1）【数据范围与约定】1≤N≤5000,1≤S≤50,1≤Ti,Ci≤100
2）【数据范围与约定】1≤N≤100000,1≤S≤100,1≤Ti,Ci≤100
3）【数据范围与约定】1≤N≤300000,1≤S≤256,-256≤Ti≤256,1≤Ci≤100
Way 1:
求出sumT,sumC两个前缀和数组,设f[i][j]为前i个任务分成j批的最小费用,
可得f[i][j]=min(f[k][j-1]+(j*S+sumT[i])*(sumC[i]-sumC[k]))
简单dp：
#include<bits/stdc++.h> using namespace std; #define why 5005 #define inf 0x3f3f3f3f long long n,S,t[why],c[why],sumt[why],sumc[why]; unsigned int ans=inf,f[why][why];//long long爆空间 inline long long redn() { long long ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int main() { n=redn(); S=redn(); for(long long i=1;i<=n;++i) { t[i]=redn(); c[i]=redn(); sumt[i]=sumt[i-1]+t[i]; sumc[i]=sumc[i-1]+c[i]; } memset(f,0x3f,sizeof(f)); for(long long i=1;i<=n;++i)f[i][1]=(sumt[i]+S)*sumc[i]; for(long long i=2;i<=n;++i) { for(long long j=2;j<=i;++j) { long long minj=inf; for(long long k=0;k<i;++k) { minj=min(minj,f[k][j-1]+(S*j+sumt[i])*(sumc[i]-sumc[k])); } f[i][j]=minj; } } for(long long i=1;i<=n;++i) { ans=min(ans,f[n][i]); } printf("%lld",ans); return 0; }
时间复杂度:O(n^3)
实际得分：80（任务安排1）
Way 2:
#include<bits/stdc++.h> using namespace std; #define why 5005 #define inf 0x3f3f3f3f long long n,S,sumt[why],sumc[why],f[why]; inline long long redn() { long long ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int main() { long long _1; n=redn(); S=redn(); for(long long i=1;i<=n;++i) { _1=redn(); sumt[i]=sumt[i-1]+_1; _1=redn(); sumc[i]=sumc[i-1]+_1; } memset(f,0x3f,sizeof(f)); f[0]=0; for(long long i=1;i<=n;++i) { for(long long k=0;k<i;++k) { f[i]=min(f[i],f[k]+sumt[i]*(sumc[i]-sumc[k])+S*(sumc[n]-sumc[k])); } } printf("%lld",f[n]); return 0; }
时间复杂度:O(n^2)
实际得分：100（任务安排1）/83（任务安排2）
Way 3:
朴素算法打好了,斜率优化就成功了一半。。。
核心方程（Way2）为f[i]=min(f[i],f[k]+sumt[i]*(sumc[i]-sumc[k])+S*(sumc[n]-sumc[k]))
∴可以推出f[j]=f[i]-sumt[i]*sumc[i]+(sumt[i]+S)*sumc[j]-S*sumc[n]
令f[j]=y,sumc[j]=x
∴k=sumt[i]+S,b=f[i]-S*sumc[n]-sumt[i]*sumc[i]
∵k单调递增
可用单调队列维护斜率单调递增,则最优决策j为截距最小时决策(队首),可O(1)求出当前f[i]
#include<bits/stdc++.h> using namespace std; #define why 100005 #define inf 0x3f3f3f3f long long n,S,sumt[why],sumc[why],f[why],q[why]; inline long long redn() { long long ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int main() { long long _1,l=1,r=1; q[1]=0; n=redn(); S=redn(); for(long long i=1;i<=n;++i) { _1=redn(); sumt[i]=sumt[i-1]+_1; _1=redn(); sumc[i]=sumc[i-1]+_1; } memset(f,0x3f,sizeof(f)); f[0]=0; for(long long i=1;i<=n;++i) { while(l<r&&f[q[l+1]]-f[q[l]]<=(S+sumt[i])*(sumc[q[l+1]]-sumc[q[l]]))++l; f[i]=f[q[l]]-(S+sumt[i])*sumc[q[l]]+sumt[i]*sumc[i]+S*sumc[n]; while(l<r&&(sumc[i]-sumc[q[r]])*(f[q[r]]-f[q[r-1]])>=(f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]]))--r; q[++r]=i; } printf("%lld",f[n]); return 0; }
时间复杂度:O(n)
实际得分：100（任务安排2）
Way 4:
别的数据加强都没关系,但t可能为负代表k不单调,∴必须维护整个凸壳,不必检查队首,但也代表队首不再是当前最优决策,需二分查找决策
#include<bits/stdc++.h> using namespace std; #define why 300005 #define inf 0x3f3f3f3f long long n,S,sumt[why],sumc[why],f[why],q[why],l=1,r=1; inline long long redn() { long long ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int findd(int k) { int ll,rr,mid; if(l==r)return q[l]; ll=l,rr=r; while(ll<rr) { mid=(ll+rr)>>1; if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]]))ll=mid+1; else rr=mid; } return q[ll]; } int main() { long long _1,now; q[1]=0; n=redn(); S=redn(); for(long long i=1;i<=n;++i) { _1=redn(); sumt[i]=sumt[i-1]+_1; _1=redn(); sumc[i]=sumc[i-1]+_1; } memset(f,0x3f,sizeof(f)); f[0]=0; for(long long i=1;i<=n;++i) { // while(l<r&&f[q[l+1]]-f[q[l]]<=(S+sumt[i])*(sumc[q[l+1]]-sumc[q[l]]))++l;无需如此 now=findd(S+sumt[i]); f[i]=f[now]-(S+sumt[i])*sumc[now]+sumt[i]*sumc[i]+S*sumc[n]; while(l<r&&(sumc[i]-sumc[q[r]])*(f[q[r]]-f[q[r-1]])>=(f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]]))--r; q[++r]=i; } printf("%lld",f[n]); return 0; }
时间复杂度:O(nlogn)
实际得分：100(任务安排3)
Way 5:
4)【数据范围与约定】1≤N≤300000,1≤S≤512,-512≤Ti,Ci≤512
倒序dp,但应在凸壳任意位置动态插入、查询,应用平衡树维护凸壳。。。代填:P