poj 3254 Corn Fields -- 状态压缩DP
摘要: dp[i][j]:1行到第i行的状态为j时最多的方法数
从第0行一直推到第n行
阅读全文
posted @
2009-05-15 21:17 longshen 阅读(578) |
评论 (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 阅读(2249) |
评论 (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 阅读(483) |
评论 (0) 编辑
acm博弈题 -- 个人小结
摘要: 寻找平衡状态（也称必败态， 奇异局势），（满足：任意非平衡态经过一次操作可以变为平衡态）
阅读全文
posted @
2009-05-15 09:47 longshen 阅读(3080) |
评论 (2) 编辑
【转】三类博弈
摘要: (一)巴什博奕(Bash Game): (二)威佐夫博奕(Wythoff Game):(三)尼姆博奕(Nimm Game):
阅读全文
posted @
2009-05-15 09:45 longshen 阅读(287) |
评论 (0) 编辑