tag:blogger.com,1999:blog-58347870030424875072011-04-22T07:29:34.733+08:00D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.comBlogger71100tag:blogger.com,1999:blog-5834787003042487507.post-73535673339142034272009-05-14T10:28:00.000+08:002009-05-14T10:29:40.867+08:00<table class="list"><tbody><tr class="rowOdd"><td class="runSubmitTime">2009-05-14 10:27:49</td> <td class="runJudgeStatus"> <span class="judgeReplyAC"> Accepted </span></td> <td class="runProblemId"><a href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2032">3034</a></td> <td class="runLanguage">C++</td> <td class="runTime">520</td> <td class="runMemory">15988</td> <td class="runUserName"><a href="http://acm.zju.edu.cn/onlinejudge/showUserStatus.do?userId=27691"><span style="color:#db6d00;">80%完美的日子</span></a></td></tr></tbody></table><br />LCS模型的DP。f[i][j]记录匹配度，g[i][j]记录匹配数。<br />状态转移方程f[i][j]=MAX{f[i-1][j-1]+v[i]+v[j]，f[i][j-1]，f[i-1][j]}。<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-7353567333914203427?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com1tag:blogger.com,1999:blog-5834787003042487507.post-55743615496100994412009-05-11T19:38:00.004+08:002009-05-11T20:01:42.545+08:00<table class="list"><tbody><tr class="rowOdd"><td class="runSubmitTime">2009-05-11 19:35:10</td> <td class="runJudgeStatus"> <span class="judgeReplyAC"> Accepted </span></td> <td class="runProblemId"><a href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=117">1117</a></td> <td class="runLanguage">C++</td> <td class="runTime">0</td> <td class="runMemory">212</td> <td class="runUserName"><a href="http://acm.zju.edu.cn/onlinejudge/showUserStatus.do?userId=27691"><span style="color: rgb(219, 109, 0);">80%完美的日子</span></a></td></tr></tbody></table><br />直接哈夫曼树应硬搞即可。哈夫曼树用优先队列比较方便。<br />建二叉树的时候预先暴力开个数组，结点指针就可以int，<br />避免了讨厌的指针。<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-5574361549610099441?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0tag:blogger.com,1999:blog-5834787003042487507.post-49616250546553607232009-05-09T09:15:00.003+08:002009-05-09T09:22:44.302+08:00<table class="list"><tbody><tr class="rowOdd"><td class="runSubmitTime">2009-05-09 09:14:24</td> <td class="runJudgeStatus"> <span class="judgeReplyAC"> Accepted </span></td> <td class="runProblemId"><a href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1921">2922</a></td> <td class="runLanguage">C++</td> <td class="runTime">440</td> <td class="runMemory">15888</td> <td class="runUserName"><a href="http://acm.zju.edu.cn/onlinejudge/showUserStatus.do?userId=27691"><span style="color:#db6d00;">80%完美的日子</span></a></td></tr></tbody></table><br />从每个bomb出发dfs，标记被覆盖的bomb，dfs的时候采取记忆化。<br />最后扫一遍累加未被标记（为被覆盖）的bomb即可。<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-4961625054655360723?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0tag:blogger.com,1999:blog-5834787003042487507.post-39822749601011042542009-05-08T19:44:00.003+08:002009-05-08T19:50:58.111+08:00<table class="list"><tbody><tr class="rowOdd"><td class="runSubmitTime">2009-05-08 19:40:36</td> <td class="runJudgeStatus"> <span class="judgeReplyAC"> Accepted </span></td> <td class="runProblemId"><a href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1734">2734</a></td> <td class="runLanguage">C++</td> <td class="runTime">0</td> <td class="runMemory">184</td> <td class="runUserName"><a href="http://acm.zju.edu.cn/onlinejudge/showUserStatus.do?userId=27691"><span style="color: rgb(219, 109, 0);">80%完美的日子</span></a></td></tr></tbody></table><br />别人随便乱切的dfs，我差点开hash判重。<br />一点总结，暴搜的时候，先仔细分析解空间，多传几个参数或许会更方便。<br />另外又PE一次，也不太尴尬了。<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-3982274960101104254?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0tag:blogger.com,1999:blog-5834787003042487507.post-55472854921125404922009-05-08T15:42:00.004+08:002009-05-08T17:21:19.620+08:00<table class="list"><tbody><tr class="rowOdd"><td class="runId"><br /></td> <td class="runSubmitTime">2009-05-08 15:35:25</td> <td class="runJudgeStatus"> <span class="judgeReplyAC"> Accepted </span></td> <td class="runProblemId"><a href="http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=883">1883</a></td> <td class="runLanguage">C++</td> <td class="runTime">0</td> <td class="runMemory">192</td> <td class="runUserName"><a href="http://acm.zju.edu.cn/onlinejudge/showUserStatus.do?userId=27691"><span style="color: rgb(219, 109, 0);">80%完美的日子</span></a></td></tr></tbody></table><br />这题我没有压缩状态直接硬搞，每个状态记录 词的第i位的数字（0～9）个数，<br />typedef struct<br />{<br /> double count[10];<br />}Status;<br />Status f[105];//f[i]表示第i位的状态<br />累加f[n].count[j]，j从0扫到k，即可。<br />(k+1)^n好像会超精度，其实不用怕，因为只保留小数点后5位，0.00000即可。<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-5547285492112540492?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0tag:blogger.com,1999:blog-5834787003042487507.post-31934729892550044072009-04-29T15:13:00.002+08:002009-04-29T15:49:11.899+08:00<table style="border-bottom: 1px dashed rgb(135, 155, 255);" class="table_text" width="100%" align="center" border="0" cellspacing="2"><tbody><tr align="center" bgcolor="#d7ebff"><td>2009-04-29 15:48:24</td><td><span style="color:red;">Accepted</span></td><td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=2084">2084</a></td><td>15MS</td><td>300K</td><td><a href="http://acm.hdu.edu.cn/viewcode.php?rid=1320040" target="_blank">440 B</a></td><td>C++</td><td class="fixedsize"><a href="http://acm.hdu.edu.cn/userstatus.php?user=wuxinghe">Master Jedi</a></td></tr></tbody></table><br />对于问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”，有2个选择：走左边 和 走右边。<br />做出1个选择：假设选择走左边结点k，然后再按一定路线（不必考虑具体路线，假设已知）走到底层，可以得到最优解。<br />那么随之发生的子问题是：“从左结点k出发 如何向下走到底层 使所经过的权值最大”。<br />用反证法容易证明：从第i层第j个结点出发 向下走到底层的最优路线，包含了从左结点k出发向下走到底层的最优路线。该问题具有最优子结构性质。<br />而子问题“从第i层第j个结点出发 如何向下走到底层 使所经过的权值最大”很明显具有重叠性。<br />于是自底向上DP即可解决问题。<br />f[i][j]：表示从第i层第j个结点出发向下走到底层能够得到的最大权值。<br />状态转移方程：f[i][j]=MAX(f[i+1][j],f[i+1][j+1]);<div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-3193472989255004407?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0tag:blogger.com,1999:blog-5834787003042487507.post-17064296148502123062009-04-28T13:56:00.005+08:002009-04-29T14:42:16.974+08:00<table style="border-bottom: 1px dashed rgb(135, 155, 255);" class="table_text" width="100%" align="center" border="0" cellspacing="2"><tbody><tr align="center" bgcolor="#d7ebff"><td>2009-04-27 13:44:16</td><td><span style="color:red;">Accepted</span></td><td><a href="http://acm.hdu.edu.cn/showproblem.php?pid=2670">2670</a></td><td>125MS</td><td>4204K</td><td><a href="http://acm.hdu.edu.cn/viewcode.php?rid=1313193" target="_blank">870 B</a></td><td>C++</td><td class="fixedsize"><a href="http://acm.hdu.edu.cn/userstatus.php?user=wuxinghe">Master Jedi</a></td></tr></tbody></table>把问题分为两个子问题：<br />1.选出哪k个boy；<br />2.按什么顺序选。<br />每个boy有两个属性：喜欢度 和 衰减速度。<br />其中衰减速度是关键。<br />我的感觉是：最好先选择衰减速度快的人（貌似贪心），好让总的衰减值最小。<br />因此先按衰减速度递减排序（解决子问题2），再DP（解决子问题1）。<br />其中f[i][j]表示：从前i个人中 按一定次序选出j个人 得到的最优喜欢度。<br /><iostream><algorithm><j)><f[n][k]><endl;></endl;></f[n][k]></j)></algorithm></iostream><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/5834787003042487507-1706429614850212306?l=dbwxh.blogspot.com' alt='' /></div>D.B.http://www.blogger.com/profile/15937183288513864370noreply@blogger.com0