pku 1014   已做
pku 1037   
pku 1050   已做
pku 1088   已做
pku 1141   已做
pku 1159   已做
pku 1163   已做
pku 1322   AC
                  看到題目就害怕，概率的-_-結(jié)果分析之下原來(lái)也不難
                  狀態(tài)d[i][j]表示有j種顏色,拿了i個(gè)巧克力的最優(yōu)值
                  方程: d[i+1][j+1] = d[i][j]*(c-j)/c;               (c為總顏色數(shù))
                            d[i+1][j-1] = d[i][j]*j/c;
                  由于只是保留3位小數(shù)，所以加優(yōu)化if (n>1000) n = 1000+n%2; //至于為什么要分奇偶性，這個(gè)還不太懂-_-這道算是ac一半而已
pku 2904   AC
                  dp[k][i][j]表示k個(gè)郵筒時(shí)候放鞭炮數(shù)為i..j時(shí)候的最優(yōu)值
                  轉(zhuǎn)移方程為:
                  dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};
                  狀態(tài)轉(zhuǎn)移時(shí)候就是考慮選t個(gè)鞭炮放時(shí)候爆或不爆
pku 1458   已做
pku 1579   已做 
pku 1695   AC 
                 d[i][j][k]表示到達(dá)第i個(gè)點(diǎn)時(shí)候另外兩輛車(chē)分別在點(diǎn)j和k時(shí)候的最優(yōu)值
                  方程： d[i+1][j][k] = min(d[i+1][j][k], d[i][j][k]+g[i][i+1]);
                               d[i+1][i][k] = min(d[i+1][i][k], d[i][j][k]+g[j][i+1]);
                               d[i+1][i][j] = min(d[i+1][i][j], d[i][j][k]+g[k][i+1]);
                  //初始條件d[1][1][1] = 0;
pku 1732   AC
                  線型模型，本想用trie的，結(jié)果用map偷懶了。
                  d[i] = min{d[j]} + 1      0<=j<i && j+1..i字符合法
pku 1953   已做
pku 1976   AC
                  先對(duì)區(qū)間做預(yù)處理, 后面不足的coaches補(bǔ)0;
                  d[k][j] = max{d[k-1][p]}+b[j];          0<=p<=j-m (b為處理后的區(qū)間數(shù)組,m是一臺(tái)locomotiv的容量)
                  由單調(diào)性可以在狀態(tài)轉(zhuǎn)移時(shí)候保存前一次轉(zhuǎn)移時(shí)候的最大值再和b[j-m]做比較，把O(n^2)壓縮到O(n)的時(shí)間復(fù)雜度
pku 2386   已做
pku 2479   已做
pku 2951   已做      
pku 3036   已做
pku 3014   已做
pku 2229   已做
pku 1185   AC
                  最經(jīng)典的狀態(tài)DP,我用三進(jìn)制表示每行狀態(tài)，然后遞推，結(jié)果tle,分析之后，枚舉出有效狀態(tài)，再推, 1000ms左右，
                  還是不夠 快， 張偉達(dá)的論文上有更快的算法。
pku 1276   AC
                  01背包

有空把以前的也再做一次!~