AOJ 901.snow halation

132


题目



点击显/隐题目

《snow halation》是μ’s的第二张单曲,其歌曲第二段伴奏结束后主唱穗乃果唱出“届けて”的同时,全场应援棒瞬间从白色转换成橙色。由于高度的整齐和效果的震撼,被称为“橙色的奇迹”,这也是“如果奇迹有颜色,那么一定是XX色”的最早来源。

现在,到了你来应援的时候了!

使用不同的应援形式有不同的效果(如里打、里跳、快挥、前挥、GT警报……),比如通常会GT警报后接着做里跳,这样能够让人更加沉迷到演唱会的气氛中。
经过精密的计算,我们终于得到了不同的应援形式连着对活跃气氛的贡献值(增加气氛的活跃值)。

现在给你一首歌的call表(记录应该如何应援),里面有一部分是0(代表这个动作可以自己随意选择),另一部分是非0整数,表示这个时候有规定的动作要做。
求这首歌能达到的最大气氛活跃值。
初始的气氛活跃值为0,第一个应援动作对气氛无影响。

样例解释:
2
3 5
83 86 77
15 93 35
86 92 49
3 3 3 1 2

3 3 3 1 2
没有可以自己随便选的,直接计算得到49+49+86+86=270

5 10
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
0 0 5 0 4 0 0 0 4 0

4 3 5 1 4 1 4 1 4 5
按照这样的顺序来选
可以达到最大值 93+58+42+67+69+67+69+67+93=625


第1行:组数T(非负整数,1<=T<=10)
第2行:应援动作数n,call表长度m(非负整数,0<=n,m<=100)
第3~3+n行:每行n个整数,表示在第i个动作后接j的气氛贡献值,Wi,j表示当前行第j个。(|Wi,j|<=100)
第4+n行:m个非负整数a[i],表示call表内容。(0<=a[i]<=n)
……


一行,一个整数,表示能达到的最大气氛活跃值。


2
3 5
83 86 77
15 93 35
86 92 49
3 3 3 1 2
5 10
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
0 0 5 0 4 0 0 0 4 0


270
625




题解


修改自 HDU 5074.Hatsune Miku(2014 鞍山赛区现场赛 E)

需要额外考虑活跃贡献值为负数的情况


代码


点击显/隐代码
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn = 105;
const int INF = 99999;

int n, m;
int a[maxn];
int dp[maxn][maxn];
int w[maxn][maxn];

// 初始化

void init() {
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= n; ++j)
            if (i == 1)
                dp[i][j] = 0;
            else
                dp[i][j] = -INF;
}

// 进行 dp
void f(int i, int l, int t) {
    if (dp[i][t] == -INF)
        dp[i][t] = dp[i - 1][l] + w[l][t];
    else
        dp[i][t] = max(dp[i][t], dp[i - 1][l] + w[l][t]);
}

// 枚举 t
void T(int i, int l) {
    if (a[i] == 0) {
        for (int t = 1; t <= n; ++t)
            f(i, l, t);
    } else {
        f(i, l, a[i]);
    }
}

// 枚举 l
void L(int i) {
    if (a[i - 1] == 0) {
        for (int l = 1; l <= n; ++l)
            T(i, l);
    } else {
        T(i, a[i - 1]);
    }
}

int main() {
    //freopen("in.txt","r",stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        // 读入数据
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &w[i][j]);

        for (int i = 1; i <= m; ++i)
            scanf("%d", &a[i]);

        // dp运算
        init();
        for (int i = 2; i <= m; ++i)
            L(i);

        // for (int i = 0; i <= m; ++i) {
        //     for (int j = 0; j <= n; ++j)
        //         printf("%d ", dp[i][j]);
        //     printf("\n");
        // }

        //找出最优解
        int ans = -INF;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, dp[m][i]);

        printf("%d\n", ans);
    }
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论