BestCoder Round #75 King’s Order dp：数位dp
King's Order 数位dp Source The question is from BC and hduoj 5642. My Solution 数位dp 状态： d[i][j][k] 为处理完i 个字符 , 结尾字符为′a′+j , 结尾部分已重复出现了 k 次的方案数; 边界：d[1][j][…
UVa 11400 Lighting System Design dp : 线性结构上dp LIS
Lighting System Design dp : 线性结构上dp LIS The question is from here. My Solution 首先这个题目是要保持总灯泡数不变的，一定是换一个上去才可以，是在这个情况下money-saving，而不管energy-saving。所以把…
UVa 1218 Perfect Service dp：树上dp 状态转移方程的优化
UVa 1218 Perfect Service 树上dp 状态转移方程的优化 The question is from here. 与这个题目 UVa 1220 Party at Hali-Bula dp：树的最大独立集写法很像，虽然各有不同； My Solution 状态定义：d[u][0] 表示u是服…
UVa 1220 Party at Hali-Bula dp：树的最大独立集
UVa 1220 Party at Hali-Bula dp：树的最大独立集 The question is from here. My Solution 注意点：这个题目有些测试数据是先出现father再出现son的，如 5 jack jill black black jack kar pur pur black …
UVa 12186 Another Crisis dp：树上dp
UVa 12186 Another Crisis 树上dp The question is from here. My Solution d(i)表示给上级发信至少需要多少工人。把所有子结点的d值排序然后取前c个， 对除非的处理 ★★ c = (k*T - 1) /100 +1; 用前向星储存树 每…
UVa 10003 Cutting Sticks dp : 线性dp triangulation三角剖分
UVa 10003 Cutting Sticks 线性dp triangulation三角剖分 The question is from here. My Solution 线性dp 三角剖分类题目的经典吧， 状态：d[ i ][ j ] 表示切割 i - j 这一段的最小费用 ，0 <= i < j <=…
UESTC 1131 男神的礼物 dp：最优矩阵链乘 triangulation 双dp
男神的礼物 最优矩阵链乘 triangulation 双dp Source 2015 UESTC Training for Dynamic Programming My Solution 这是一个经典的最优矩阵链乘问题，只不过单个费用会改变，像是2个dp搞在一起，是把单个的min…
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS The question is from here. My Solution d[ i ] = min{ d[ j ]+1 | is[j+1][i]是回文串 }; d[ i ] 表示0~i 内回文串的最小个数; 然后对于is[ j+1 ][ i ]…
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题 The question is from here My Solution： 刘老师给了我们那么多的数据是为了告诉我们: 歌曲的总时间不会超过 n*180-1+678 及 50*180-1+678 = 9677 并不像题中的t <= 1…
