[POJ 1180][IOI 2002]Batch Scheduling

這裡先給出$O(N^{2})$的code：

#include<cstdio>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
int N,S,T[10001],C[10001],TSUM[10001],CSUM[10001],DP[10002];
int main()
{
    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        scanf("%d",&S);
        for(int i=1;i<=N;i++)scanf("%d%d",&T[i],&C[i]),TSUM[i]=TSUM[i-1]+T[i],CSUM[i]=CSUM[i-1]+C[i];
        DP[N+1]=0;
        for(int i=N;i>=1;i--)
        {
            DP[i]=INF;
            for(int j=i;j<=N;j++)getmin(DP[i],(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])+DP[j+1]);
        }
        printf("%d\n",DP[1]);
    }
    return 0;
}

其中$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])$可以拆解成$(S+TSUM[j]-TSUM[i-1])*(CSUM[j]-CSUM[i-1])$和$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[j])$
前者代表批次執行第$i$項任務到第$j$項任務所花的成本，後者代表批次執行完第$i$項任務到第$j$項任務後害第$j+1$項以後的任務增加的成本

這樣對$DP$的定義清楚了吧^_^

可以發現，我們會枚舉$j$求$(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])+DP[j+1]$的最小值，展開後把項依照性質分離後，會變成以下形式：
1. 只受$i$影響，可以當常數：$S*CSUM[N]-S*CSUM[i-1]-TSUM[i-1]*CSUM[N]+TSUM[i-1]*CSUM[i-1]$
2. 只受$j$影響：$TSUM[j]*CSUM[N]+DP[j+1]$
3. 同時受$i$和$j$影響：$-TSUM[j]*CSUM[i-1]$

如果學過凸包優化，應該會知道要把$-TSUM[j]$當作$a$，$TSUM[j]*CSUM[N]+DP[j+1]$當作$b$，求$x=CSUM[i-1]$時，$ax+b$的最小值($ax+b$會被當作一條條的直線)

關於凸包優化這裡不再細講，網路上可以查到很多資料XD

時間複雜度：$O(N)$

code:

#include<cstdio>
#include<cassert>
using namespace std;
const int INF=2147483647;
void getmin(int &a,const int b){if(b<a)a=b;}
struct Deq
{
    int s[10002],l,r;
    void clear(){l=10002,r=10001;}
    void push_front(const int v){s[--l]=v;}
    void pop_back(){r--;}
    void pop_front(){l++;}
    int front(const int idx){return s[l+idx];}
    int back(const int idx){return s[r-idx];}
    int size(){return r-l+1;}
}DEQ;
int N,S,T[10001],C[10001],TSUM[10001],CSUM[10001],DP[10002];
double GetA(const int i){return -TSUM[i];}
double GetB(const int i){return (double)TSUM[i]*CSUM[N]+DP[i+1];}
double GetX(const int i1,const int i2)
{//ax+b=Ax+B, (a-A)x=(B-b)
    return (GetB(i2)-GetB(i1))/(GetA(i1)-GetA(i2));
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        scanf("%d",&S);
        for(int i=1;i<=N;i++)scanf("%d%d",&T[i],&C[i]),TSUM[i]=TSUM[i-1]+T[i],CSUM[i]=CSUM[i-1]+C[i];
        DP[N+1]=0;
        DEQ.clear(),DEQ.push_front(N+1);
        for(int i=N;i>=1;i--)
        {
            while(DEQ.size()>=2&&GetX(i,DEQ.front(0))>=GetX(DEQ.front(0),DEQ.front(1)))DEQ.pop_front();
            DEQ.push_front(i);
            while(DEQ.size()>=2&&GetX(DEQ.back(1),DEQ.back(0))>=CSUM[i-1])DEQ.pop_back();
            const int j=DEQ.back(0);
            DP[i]=(S*CSUM[N]-S*CSUM[i-1]-TSUM[i-1]*CSUM[N]+TSUM[i-1]*CSUM[i-1])+(TSUM[j]*CSUM[N]+DP[j+1])-(TSUM[j]*CSUM[i-1]);
            //DP[i]=(S+TSUM[j]-TSUM[i-1])*(CSUM[N]-CSUM[i-1])+DP[j+1]
            //=S*CSUM[N]-S*CSUM[i-1]+TSUM[j]*CSUM[N]-TSUM[j]*CSUM[i-1]-TSUM[i-1]*CSUM[N]+TSUM[i-1]*CSUM[i-1]+DP[j+1]
            //=(S*CSUM[N]-S*CSUM[i-1]-TSUM[i-1]*CSUM[N]+TSUM[i-1]*CSUM[i-1])+(TSUM[j]*CSUM[N]+DP[j+1])-(TSUM[j]*CSUM[i-1])
            //a=-TSUM[j],b=TSUM[j]*CSUM[N]+DP[j+1],x=CSUM[i-1]
            //minimize ax+b
        }
        printf("%d\n",DP[1]);
    }
    return 0;
}