poj 3254 Corn Fields -- 狀態(tài)壓縮DP      摘要: dp[i][j]:1行到第i行的狀態(tài)為j時(shí)最多的方法數(shù)
從第0行一直推到第n行
  閱讀全文

poj 1947 Rebuilding Roads -- 樹形DP      摘要: dp[s][i]:記錄s結(jié)點(diǎn)，要得到一棵j個(gè)節(jié)點(diǎn)的子樹去掉的最少邊數(shù)
考慮其兒子k
1）如果不去掉k子樹，則
dp[s][i] = min(dp[s][j]+dp[k][i-j]) 0 <= j <= i

2）如果去掉k子樹，則
dp[s][i] = dp[s][i]+1
總的為
dp[s][i] = min (min(dp[s][j]+dp[k][i-j]) , dp[s][i]+1 )  閱讀全文

poj 1837 Balance -- 動(dòng)態(tài)規(guī)劃      摘要: dp[i][mm+k]:取前i個(gè)時(shí)，天平處于k狀態(tài)的方法數(shù)
mm+k:< mm為左邊重， > mm 為右邊重

dp[i][mm+k] +=
dp[i-1][mm + k-weight[i]*arm[j]], (j:1->c)};   閱讀全文

poj 2192 Zipper -- 簡(jiǎn)單DP

poj 2186 Popular Cows -- 強(qiáng)連通分支      摘要: 研究了Lynncui牛的代碼，才知道解題思路：
先Tarjan強(qiáng)連通縮點(diǎn)，（假設(shè)共n2個(gè)）得到的id[i]編號(hào)為0的分支，其出度為0（有可能是Popular Cows）。
再判斷其他強(qiáng)連通分支是否有出度
1）如果其中有一個(gè)分支沒有出度，則0分支不可能是Popular Cows（considered popular by every other cow）
2）如果其他所有強(qiáng)連通分支都有出度，  閱讀全文

poj 2762 Going from u to v or from v to u? -- 強(qiáng)連通      摘要: 思路模糊時(shí)看了DieIng大牛的思路，寫了出來...
思路：Tarjan算法計(jì)算強(qiáng)連通分支，然后縮點(diǎn)，再求其拓?fù)湫颉?
（假設(shè)求得的拓?fù)湫虼鎯?chǔ)在topo[MAX]中） topo[i] 與 topo[i+1] 存在邊連通(i到i+1 或i+1到i)，則定有i到i+1的邊。
而如果每個(gè)topo[i] 與 topo[i+1] 都存在邊連通(即有i到i+1的邊)時(shí)，topo[i] 到任意topo[j]便都要邊連通。
  閱讀全文

poj 1191 棋盤分割 -- 動(dòng)態(tài)規(guī)劃      摘要: dp[k][x1][y1][x2][y2]:左上角坐標(biāo)為(x1,y1)，右下角坐標(biāo)為(x2,y2)
的棋盤，設(shè)它把切割k次以后得到的k+1塊矩形的總分平方和最小值.

s[x1][y1][x2][y2]:左上角坐標(biāo)為(x1,y1)，右下角坐標(biāo)為(x2,y2)
的棋盤的總和的平方


dp[k][x1][y1][x2][y2] =
1)按橫的劃分： min(dp[k-1][x1][y1][f][y2]+s[f+1][y1][x2][y2]
, dp[k-1][f+1][y1][x2][y2]+s[x1][y1][f][y2]);

2)按豎的劃分： min(dp[k-1][x1][y1][x2][f]+s[x1][f+1][x2][y2]
, dp[k-1][x1][f+1][x2][y2]+s[x1][y1][x2][f]);
  閱讀全文