HDU 5074 Hatsune Miku

老实说有点崩溃，一场训练赛，3道dp都没出，两道还是全世界都A了
毫无疑问，又落后一截……
实在不明白他们的dp为什么这么6……

题意：
给你一个序列 ( a_1 a_2 a_3 a_4 …… a_n )
要你求相邻两个元素在矩阵中的数值和。
矩阵已给定，但是如果序列元素为负数，则可以为任意元素。

思路：
渐渐觉得dp就是暴力……
四种情况

<code class="language-null">#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 110;

int mat[maxn][maxn], dp[maxn][maxn];
int ary[maxn];

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, m) range(j, 1, m) scanf("%d", &mat[i][j]);
        range(i, 1, n) scanf("%d", ary + i);
        fill(dp, 0);
        range(i, 2, n)
        {
            if (ary[i - 1] < 0)
                if (ary[i] < 0)
                    range(j, 1, m) range(k, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j]);
                else
                    range(j, 1, m) dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]]);
            else if (ary[i] < 0)
                range(j, 1, m) dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j]);
            else
                dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]];
        }
        int ans = 0;
        range(i, 1, m) ans = max(ans, dp[n][i]);
        printf("%d\n", ans);
    }
    return 0;
}