题目

Description

Hatsune Miku is a popular virtual singer. It is very popular in both Japan and China. Basically it is a computer software that allows you to compose a song on your own using the vocal package.

Today you want to compose a song, which is just a sequence of notes. There are only m different notes provided in the package. And you want to make a song with n notes.

Also, you know that there is a system to evaluate the beautifulness of a song. For each two consecutive notes a and b, if b comes after a, then the beautifulness for these two notes is evaluated as score(a, b).

So the total beautifulness for a song consisting of notes a 1, a 2, . . . , a n, is simply the sum of score(a i, a i+1) for 1 ≤ i ≤ n - 1.

Now, you find that at some positions, the notes have to be some specific ones, but at other positions you can decide what notes to use. You want to maximize your song’s beautifulness. What is the maximum beautifulness you can achieve

Input

The first line contains an integer T (T ≤ 10), denoting the number of the test cases.

For each test case, the first line contains two integers n(1 ≤ n ≤ 100) and m(1 ≤ m ≤ 50) as mentioned above. Then m lines follow, each of them consisting of m space-separated integers, the j-th integer in the i-th line for score(i, j)( 0 ≤ score(i, j) ≤ 100). The next line contains n integers, a 1, a 2, . . . , a n (-1 ≤ a i ≤ m, a i ≠ 0), where positive integers stand for the notes you cannot change, while negative integers are what you can replace with arbitrary notes. The notes are named from 1 to m.

Output

For each test case, output the answer in one line.

Sample Input

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

Sample Output

270
625

题解

有不同的节奏,给出每两个节奏的分值,计算一首歌的最高得分
正数代表节奏序号,负数代表可以填入任意一个节奏

由于歌曲长达 100 节奏种类多达 50
如果所有情况都列举出来,可能数太多
采用动态规划来处理

使用 dp[i][j] 来记录前 i 个节奏且第 i 个节奏为 j 的最高分数

循环到 i 时,如果 i-1 是不确定的,循环所有可能计算
如果是确定的只需要计算这一种情况
再同理判断 i ,两个数都得到后调用公式即可

由于此处嵌套比较乱,可以写成函数来使思路更加清晰
(本来有 bug 改成函数瞬间就没 bug 了)

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxm = 55;
const int maxn = 105;

int n,m;
int score[maxm][maxm];
int note[maxn];
int dp[maxn][maxm];

void DP(int i,int ln,int tn) {
    dp[i][tn] = max(dp[i][tn],dp[i - 1][ln] + score[ln][tn]);
}

void TN(int i,int ln) {
    if(note[i] < 0) {
        for(int j = 1;j <= m;j++)
            DP(i,ln,j);
    } else {
        DP(i,ln,note[i]);
    }
}

void LN(int i) {
    if(note[i - 1] < 0) {
        for(int j = 1;j <= m;j++)
            TN(i,j);
    } else {
        TN(i,note[i - 1]);
    }
}

void Do() {

    cin >> n >> m;
    for(int i = 1;i <= m;i++)
        for(int j = 1;j <= m;j++)
            cin >> score[i][j];
    for(int i = 0;i < n;i++)
        cin >> note[i];

    memset(dp,0,sizeof(dp));
    for(int i = 1;i < n;i++) {
        LN(i);
    }

    int Max = 0;
    for(int i = 1;i <= m;i++)
        Max = max(Max,dp[n - 1][i]);

    cout << Max << endl;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int T;
    cin >> T;
    while(T--)
        Do();

    return 0;
}