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:
何必增加批數j？為了知道機器啟動過多少次（以便累加S）.
那如果我們每次計算S時累加到後面的情況，會怎樣？
（會O(n^2)優化）
狀态轉移方程：
f[i]=min(f[k]+sumT[i]*(sumC[i]-sumC[k])+S*(sumC[n]-sumC[k]))
#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