hdu 5074 Hatsune Miku DP题目

题目传送门http://acm.hdu.edu.cn/showproblem.php?pid=5074

$dp[i][j] =$ 表示数列前$i$个数以$j$结尾的最大分数 $dp[i][j] = -1$ 表示不可能取到。

当$b[i] = -1$ 时:

$$dp[i][j] = \max(dp[i][j],dp[i-1][k] + scores[k][j])$$

$$(1 <= j <= m,dp[i-1][k] != -1)$$

当$b[i] != -1$ 时:

$$dp[i][j] = -1 (j != b[i])$$

$$dp[i][b[i]] = \max(b[i][b[i]],dp[i-1][k] + scores[k][b[i]])$$

$$ (1 <= j <= m,dp[i-1][k] != -1)$$

复杂度为$$O(n \times m^2)$$

鞍山赛区烙下的阴影，当时竟然老想着用dfs来暴力过去，脑洞真是好大，图样图森破，dp能力太差了，回来补题的时候还是不会做，具体方法是参照数一巨巨的,具体的可以看他的博客,然后自己写了一份代码.

/*********************************
Author: jusonalien
Email : [e-mail]
school: South China Normal University
Origin: HDU 5074
*********************************/
#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <vector>
using namespace std;
int t,n,m;
int scores[110][110];
int a[110];
int dp[110][110];
void solve(){
    if(a[1] != -1)
        for(int i = 1;i <= m;++i){
            if(i != a[1])
                dp[1][i] = -1;
        }
        for(int i = 2;i <= n;i++){
            if(a[i] == -1){
                for(int j = 1;j <= m;++j)
                    for(int k = 1;k <= m;++k)
                    if(dp[i-1][k] != -1)
                        dp[i][j] = max(dp[i][j],dp[i-1][k]+scores[k][j]);
            }
            else{
                for(int j = 1;j <= m;++j)
                    if(dp[i-1][j] != -1)
                        dp[i][a[i]] = max(dp[i][a[i]],dp[i-1][j]+scores[j][a[i]]);
                for(int k = 1;k <= m;++k)
                    if(k != a[i])
                        dp[i][k] = -1;
            }
        }
        int ans = 0;
        for(int i = 1;i <= m;++i)
            ans = max(ans,dp[n][i]);
        printf("%d\n",ans);
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= m;i++)
            for(int j = 1;j <= m;j++) scanf("%d",&scores[i][j]);
        for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
        solve();
    }
    return 0;
}
/*
2
5 3
83 86 77
15 93 35
86 92 49
3 3 3 1 2
10 5
36 11 68 67 29
82 30 62 23 67
35 29 2 22 58
69 67 93 56 11
42 29 73 21 19
-1 -1 5 -1 4 -1 -1 -1 4 -1
*/