HDU 5074 Hatsune Miku 2014 ACM/ICPC AnShan
题意
使用$m$种音符组成一个长为$n$的歌曲，定义两个相邻音符$(a, b)$的美丽度是$score[a][b]$，而一个长为$n$的歌曲$a[1..n]$的美丽度是其所有的相邻音符$ (a_i, a_{i+1}) $（共有$n - 1$个）美丽度的和。现在已知在歌曲的某些位置的音符已经被钦定了，问能够达到的最大的美丽度是多少？
思路
代码
常规的暴力法就是对每一位枚举并计算美丽度，复杂度是\( m^n \)。但实际上可以dp来做。
定义dp[i][j]是第i个音符选j时前i个序列的最大美丽度。
然后在dp的时候考虑i - 1和i分别是-1和正数的四种情况：
- 当
i - 1位置和i位置全部已知的时候，dp[i][j]是个定值。 - 当
i - 1位置未知、i位置已知为j的时候，dp[i][j]就是在i - 1位置枚举所有的值取大的更新，继续维护dp数组的性质。 i位置未知时候，问题实际上分解为m个小问题，令j=[1..m]，然后按照2的方法计算。
有一个坑就是最后一个数可能不是-1，所以输出答案的时候先判断是-1了，再比较输出最大的dp[n][j]。
