HDU 5074 Hatsune Miku

HDU 5074 Hatsune Miku 2014 ACM/ICPC AnShan

题意

使用$m$种音符组成一个长为$n$的歌曲,定义两个相邻音符$(a, b)$的美丽度是$score[a][b]$,而一个长为$n$的歌曲$a[1..n]$的美丽度是其所有的相邻音符$ (ai, a{i+1}) $(共有$n - 1$个)美丽度的和。现在已知在歌曲的某些位置的音符已经被钦定了,问能够达到的最大的美丽度是多少?

思路

代码
常规的暴力法就是对每一位枚举并计算美丽度,复杂度是\( m^n \)。但实际上可以dp来做。
定义dp[i][j]是第i个音符选j时前i个序列的最大美丽度。
然后在dp的时候考虑i - 1i分别是-1和正数的四种情况:

  1. i - 1位置和i位置全部已知的时候,dp[i][j]是个定值。
  2. i - 1位置未知、i位置已知为j的时候,dp[i][j]就是在i - 1位置枚举所有的值取大的更新,继续维护dp数组的性质。
  3. i位置未知时候,问题实际上分解为m个小问题,令j = [1..m],然后按照2的方法计算。

有一个坑就是最后一个数可能不是-1,所以输出答案的时候先判断是-1了,再比较输出最大的dp[n][j]