# 题目

{% fold 点击显/隐题目 %}

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

2
3 5
83 86 77
15 93 35
86 92 49
3 3 3 1 2

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

4 3 5 1 4 1 4 1 4 5

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
{% endfold %}

# 代码

{% fold 点击显/隐代码 %}```cpp snow halation https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
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;
``````

}

`{% endfold %}`