A Contest to Celebrate Girlfriend’s Birthday by Staginner

Problem 1: Cut the rope II

题意: 把长度为L的线段进行分割，分割后每一段都不相同的方案数。L<=50000

思路: dp比较赞，可以发现因为每一段都不相同所以至多会有 x段，x*(x+1)/2 = L。x最大值在320左右。

dp[i][j][k] i<=320,j<=50000 k<2

• k=0 表示现有i段用掉j的长度时不存在长度为1的段的方案数
• k=1 表示现有i段用掉j的长度时存在长度为1的段的方案数

转移:

• dp[i][j][0] = dp[i][j-i][0] + dp[i][j-i][1] 表示当前每一段长度都加1
• dp[i][j][1] = dp[i-1][j-1][0] 表示新增一段长度为1的

复杂度: 320*50000

Problem 2: Shortest Path

题意: 求从1到n边长度严格递增的最短路。

解法1: 把边按长度排序后，长度相同的一组一组加入，然后来更新相应的点。

解法2: 这个方法比较麻烦。

重建图：每一条无向边先拆成两条有向的，然后把每条边的两个端点当做新的节点。对于那些原来是同一个节点的新节点，按边的长度再按边先出后入得原则排序，保证前面的节点一定能更新后面的节点，然后在相邻两个之间连一条长度为0的有向边，做最短路即可。

Contest solutions from a birthday celebration contest, 2013.