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

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

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

ary[i-1] < 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][k] + mat[k][j])
ary[i-1] < 0 && ary[i] > 0dp[i][ary[i]] = max(dp[i][ary[i]], dp[i - 1][j] + mat[j][ary[i]])
ary[i-1] > 0 && ary[i] < 0dp[i][j] = max(dp[i][j], dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][j])
ary[i-1] > 0 && ary[i] > 0dp[i][ary[i]] = dp[i - 1][ary[i - 1]] + mat[ary[i - 1]][ary[i]]

AC Code

#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;
}
Categories: 简单DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

简单DP

HDU 6143 Killer Names

昨天的多校应该是团队合作最失败的一次…… 一开始过题人数最多的那道题许 Read more…

简单DP

POJ 1661 Help Jimmy

好题!!!! 这道题我整整想了一个晚上,怎么说呢,应该还是我从一开始就 Read more…

简单DP

POJ 1692 Crossed Matchings

坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑 Read more…