poj 3254 Corn Fields -- 状态压缩DP      摘要: dp[i][j]:1行到第i行的状态为j时最多的方法数
从第0行一直推到第n行
  阅读全文

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 )  阅读全文

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)};   阅读全文

poj 2192 Zipper -- 简单DP

poj 2186 Popular Cows -- 强连通分支      摘要: 研究了Lynncui牛的代码，才知道解题思路：
先Tarjan强连通缩点，（假设共n2个）得到的id[i]编号为0的分支，其出度为0（有可能是Popular Cows）。
再判断其他强连通分支是否有出度
1）如果其中有一个分支没有出度，则0分支不可能是Popular Cows（considered popular by every other cow）
2）如果其他所有强连通分支都有出度，  阅读全文

poj 2762 Going from u to v or from v to u? -- 强连通      摘要: 思路模糊时看了DieIng大牛的思路，写了出来...
思路：Tarjan算法计算强连通分支，然后缩点，再求其拓扑序。
（假设求得的拓扑序存储在topo[MAX]中） topo[i] 与 topo[i+1] 存在边连通(i到i+1 或i+1到i)，则定有i到i+1的边。
而如果每个topo[i] 与 topo[i+1] 都存在边连通(即有i到i+1的边)时，topo[i] 到任意topo[j]便都要边连通。
  阅读全文

poj 1191 棋盘分割 -- 动态规划      摘要: dp[k][x1][y1][x2][y2]:左上角坐标为(x1,y1)，右下角坐标为(x2,y2)
的棋盘，设它把切割k次以后得到的k+1块矩形的总分平方和最小值.

s[x1][y1][x2][y2]:左上角坐标为(x1,y1)，右下角坐标为(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]);
  阅读全文