HDU 5074 Hatsune Miku：DP 求最大美感值

題目大意

有 m 種音符，需譜寫長度為 n 的樂曲。某些位置固定音符，其余可自由選擇。相鄰音符 (a,b) 有美感分 score(a,b)。求最大總美感。

DP 定義

dp[i][k]：前 i 個位置，第 i 位置選音符 k 的最大美感。
轉移：
dp[i][k] = max_j ( dp[i-1][j] + score(j,k) )
若第 i 位置固定為 x，則只更新 k=x。

代碼

int dis[55][55], a[110], dp[110][55];
int main() {
    int T; scanf("%d",&T);
    while (T--) {
        memset(dp,-1,sizeof(dp));
        int n,m; scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) scanf("%d",&dis[i][j]);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        if (a[1]!=-1) dp[1][a[1]]=0;
        else for (int i=1;i<=m;i++) dp[1][i]=0;
        for (int i=2;i<=n;i++) {
            for (int j=1;j<=m;j++) if (dp[i-1][j]!=-1) {
                if (a[i]!=-1) dp[i][a[i]] = max(dp[i][a[i]], dp[i-1][j]+dis[j][a[i]]);
                else for (int k=1;k<=m;k++) dp[i][k] = max(dp[i][k], dp[i-1][j]+dis[j][k]);
            }
        }
        int ans=-INF;
        for (int i=1;i<=m;i++) ans=max(ans,dp[n][i]);
        printf("%d\n",ans);
    }
    return 0;
}

複雜度

O(n·m²)，n≤100, m≤50，約 2.5×10⁵，極快。