[IOI2002]任務安排
★☆ 輸入文件：batch.in 輸出文件：batch.out 簡單對比
時間限制：1 s 內存限制：128 MB
N個任務排成一個序列在一臺機器上等待完成（順序不得改變），這N個任務被分成若干批，每批包含相鄰的若干任務。從時刻0開始，這些任務被分批加工，第i個任務單獨完成所需的時間是Ti。在每批任務開始前，機器需要啟動時間S，而完成這批任務所需的時間是各個任務需要時間的總和（同一批任務將在同一時刻完成）。每個任務的費用是它的完成時刻乘以一個費用系數(shù)Fi。請確定一個分組方案，使得總費用最小。
例如：S=1；T={1,3,4,2,1}；F={3,2,3,3,4}。如果分組方案是{1,2}、{3}、{4,5}，則完成時間分別為{5,5,10,14,14}，費用C={15,10,30,42,56}，總費用就是153。
輸入
第一行是N(1<=N<=5000)。
第二行是S(0<=S<=50)。
下面N行每行有一對數(shù)，分別為Ti和Fi，均為不大于100的正整數(shù)，表示第i個任務單獨完成所需的時間是Ti及其費用系數(shù)Fi。
輸出
一個數(shù)，最小的總費用。
輸入樣例
5
1
1 3
3 2
4 3
2 3
1 4
輸出樣例
153

/* DP. n^2做法. 這題沒想出來. 正解要考慮后效性. 因為當我們選擇一個任務作為開始的時候 它必然會對后面的決策產生影響. 所以我們先把后效性的貢獻算出來累加進去. 方程長這樣 f[i]=min(f[i],f[j-1]+(sumw[i]-sumw[j-1])*sumt[i]+S*(sumw[n]-sumw[j-1])) sumw表示前綴F[i],sumt表示前綴t[i]. */ #include<iostream> #include<cstring> #include<cstdio> #define MAXN 5010 using namespace std; int n,S,F[MAXN],f[MAXN],sumt[MAXN],sumw[MAXN]; int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f; } void slove() {for(int i=1;i<=n;i++) f[i]=1e9;f[0]=0;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++)f[i]=min(f[i],f[j-1]+(sumw[i]-sumw[j-1])*sumt[i]+S*(sumw[n]-sumw[j-1]));}printf("%d",f[n]); } int main() {freopen("batch.in","r",stdin);freopen("batch.out","w",stdout);int x;n=read(),S=read();for(int i=1;i<=n;i++){x=read(),F[i]=read();sumt[i]=sumt[i-1]+x;sumw[i]=sumw[i-1]+F[i];}slove();return 0; }

轉載于:https://www.cnblogs.com/nancheng58/p/10068029.html

總結

以上是生活随笔為你收集整理的Cogs 376. [IOI2002]任务安排(后效性DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。