poj 3254 Corn Fields -- 狀態壓縮DP
摘要: dp[i][j]:1行到第i行的狀態為j時最多的方法數
從第0行一直推到第n行
閱讀全文
posted @
2009-05-15 21:17 longshen 閱讀(582) |
評論 (0) 編輯
poj 1947 Rebuilding Roads -- 樹形DP
摘要: dp[s][i]:記錄s結點，要得到一棵j個節點的子樹去掉的最少邊數
考慮其兒子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 )
閱讀全文
posted @
2009-05-15 11:37 longshen 閱讀(2255) |
評論 (2) 編輯
poj 1837 Balance -- 動態規劃
摘要: dp[i][mm+k]:取前i個時，天平處于k狀態的方法數
mm+k:< mm為左邊重， > mm 為右邊重
dp[i][mm+k] +=
dp[i-1][mm + k-weight[i]*arm[j]], (j:1->c)};
閱讀全文
posted @
2009-05-15 09:53 longshen 閱讀(488) |
評論 (0) 編輯
acm博弈題 -- 個人小結
摘要: 尋找平衡狀態（也稱必敗態， 奇異局勢），（滿足：任意非平衡態經過一次操作可以變為平衡態）
閱讀全文
posted @
2009-05-15 09:47 longshen 閱讀(3102) |
評論 (2) 編輯
【轉】三類博弈
摘要: (一)巴什博奕(Bash Game): (二)威佐夫博奕(Wythoff Game):(三)尼姆博奕(Nimm Game):
閱讀全文
posted @
2009-05-15 09:45 longshen 閱讀(292) |
評論 (0) 編輯