[ZJ d229]IOI研習營模考2-4砝碼

用暴搜寫了一個會TLE的code (請看這裡)

然後就在自己的電腦上跑出所有答案

再另寫個程式把輸出整理成code的樣子

稍作修改......完成！

這code看起來真是優美(?)

p.s.求正解作法啊......我真的看不出甚麼規律QQ......

code:

[ZJ d229]IOI研習營模考2-4砝碼 (答案產生器)

不是題解的題解在這裡
這份暴搜code在我的電腦上跑了一小時......
然後......ㄎㄎ你知道的 ^_^

code:

[HOJ 136][IOI 2007]Training

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

換句話說，題目希望不產生偶環的前提下，總權重最大化
感覺會超多奇環相互交錯再一起耶......好複雜QQ

我們先來討論兩個奇環的情況
1. 不相交：合法情況，之後再深入討論
2. 相交於一點：合法情況，之後再深入討論
3. 重合於任何邊：形成偶環了，不合法！
(原來奇環也只有這樣嘛www)

那些會在樹上形成偶環的非樹邊可以直接刪除了

我們來嘗試構造一個樹形$DP$
首先，我們必須避免同一條邊被多個環同時使用
因此，狀態中必須包含哪些邊被用過了
由於每個點的度數不超過$10$
因此我們可以利用位元壓縮的技巧，用$DP[u][s]$代表以$u$為節點的子樹中，連到$u$的邊 (包含樹邊和非樹邊) 的子集合$s$ (用$bit\ mask$表示) 被用過了，總權重最多多少

於是，我們可以枚舉所有「樹上路徑」會通過$u$的邊$e$，然後用以下方式直接算出每個$DP[u][s]$：

圖片來源：http://www.ioinformatics.org/locations/ioi07/contest/solutions.pdf

其中除了以下這個 (稱作$subtree$) 需要遞迴計算之外，其他的都已經在先前遞迴到子樹時計算好了

可是這樣要計算$subtree$的時候還要想辦法把兩端都在$subtree$內的非樹邊分離出來
想一想複雜度好像很容易又爛掉了QQ

沒關係，不用遞迴了，我們先算好只加一個環的部分

然後依照$bit\ mask$中$1$的數量由小到大更新$DP[u]$ (這時候如果用到的邊沒有重複就可以直接相加來更新更大的$DP[u]$了)
為了節省時間，只更新「加一個環」(用掉兩條邊) 和「加一棵子樹」(用掉一條邊) 的情況，然後順著$DP[u]$的更新順序就可以把所有情況都考慮進去了

小提醒：請記得答案是所有邊的權重總和減掉算出來的$DP$

時間複雜度：$O(N^{2}+NM+2^{10}M)$ (預處理從$u$走到$v$要先走連到$u$的第幾條邊、預處理一條邊是$u$的第幾條邊、更新$DP$)

code:

[HOJ 136][IOI 2007]Training (純code不含題解)

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～
題解在這裡

code:

[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: