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即可。

Hdu/Hdoj 2048 数塔

2009-04-29 15:48:24

Accepted

2084

15MS

300K

440 B

C++

Master Jedi

对于问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”，有2个选择：走左边 和 走右边。
做出1个选择：假设选择走左边结点k，然后再按一定路线（不必考虑具体路线，假设已知）走到底层，可以得到最优解。
那么随之发生的子问题是：“从左结点k出发 如何向下走到底层 使所经过的权值最大”。
用反证法容易证明：从第i层第j个结点出发 向下走到底层的最优路线，包含了从左结点k出发向下走到底层的最优路线。该问题具有最优子结构性质。
而子问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”很明显具有重叠性。
于是自底向上DP即可解决问题。
f[i][j]：表示从第i层第j个结点出发向下走到底层能够得到的最大权值。
状态转移方程：f[i][j]=MAX(f[i+1][j],f[i+1][j+1]);

Hdu/Hdoj 2670 Girl Love Value

2009-04-27 13:44:16

Accepted

2670

125MS

4204K

870 B

C++

Master Jedi

把问题分为两个子问题：
1.选出哪k个boy；
2.按什么顺序选。
每个boy有两个属性：喜欢度 和 衰减速度。
其中衰减速度是关键。
我的感觉是：最好先选择衰减速度快的人（貌似贪心），好让总的衰减值最小。
因此先按衰减速度递减排序（解决子问题2），再DP（解决子问题1）。
其中f[i][j]表示：从前i个人中 按一定次序选出j个人 得到的最优喜欢度。