Hatsune Miku
Problem's Link: http://acm.hdu.edu.cn/showproblem.php?pid=5074
Mean:
有m种音符(note)，现在要从这m种音符中选出n个来组成一首歌，相邻两个音符之间会有一个评分的方式，即score(i,j)，而score(i,j)题目已经给出，现在要你按照题目的规定来选出n个音符来使得最终的分数最高。
analyse:
鞍山赛区第二大水题，很简单的dp。
具体思路：dp[i][j]表示第i个音符选择的是第j种。
那么就很容易得出状态转移方程：dp[i][j]=max(dp[i][j],dp[i+1][j]+v[j][k]).(详见代码)
Time complexity: O(n*m*m)
Source code:
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-11-15-21.40
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
/**< dp[i][j]代表第i个note选择第j种 */
int v[60][60],a[105],dp[105][105];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);
// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
cin>>v[i][j];
for(int i=1;i<=n;++i)
cin>>a[i];
memset(dp,0,sizeof dp);
for(int i=n-1;i>=0;--i)/**< 要选出n个数 */
{
for(int j=0;j<=m;++j)/**< 其中每个数都对应着m选法 */
{
if(a[i+1]<0)/**< 可以*选 */
{
for(int k=1;k<=m;++k)
dp[i][j]=max(dp[i][j],dp[i+1][k]+v[j][k]);
}
else/**< 已经固定的 */
{
dp[i][j]=v[j][a[i+1]]+dp[i+1][a[i+1]];
}
}
}
cout<<dp[0][0]<<endl;
}
return 0;
}
/*
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
*/