Zju/Zoj 3034 The Bridges of Kolsberg

2009-05-14 10:27:49

Accepted

3034

C++

520

15988

80%完美的日子

LCS模型的DP。f[i][j]记录匹配度，g[i][j]记录匹配数。
状态转移方程f[i][j]=MAX{f[i-1][j-1]+v[i]+v[j]，f[i][j-1]，f[i-1][j]}。

Zju/Zoj 1117 Entropy

2009-05-11 19:35:10

Accepted

1117

C++

0

212

80%完美的日子

直接哈夫曼树应硬搞即可。哈夫曼树用优先队列比较方便。
建二叉树的时候预先暴力开个数组，结点指针就可以int，
避免了讨厌的指针。

Zju/Zoj 2922 Bombs

2009-05-09 09:14:24

Accepted

2922

C++

440

15888

80%完美的日子

从每个bomb出发dfs，标记被覆盖的bomb，dfs的时候采取记忆化。
最后扫一遍累加未被标记（为被覆盖）的bomb即可。

Zju/Zoj 2734 Exchange Cards

2009-05-08 19:40:36

Accepted

2734

C++

0

184

80%完美的日子

别人随便乱切的dfs，我差点开hash判重。
一点总结，暴搜的时候，先仔细分析解空间，多传几个参数或许会更方便。
另外又PE一次，也不太尴尬了。

Zju/Zoj 1883 Tight Words

2009-05-08 15:35:25

Accepted

1883

C++

0

192

80%完美的日子

这题我没有压缩状态直接硬搞，每个状态记录 词的第i位的数字（0～9）个数，
typedef struct
{
double count[10];
}Status;
Status f[105];//f[i]表示第i位的状态
累加f[n].count[j]，j从0扫到k，即可。
(k+1)^n好像会超精度，其实不用怕，因为只保留小数点后5位，0.00000即可。