题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5074
解题报告:给出一个长度为n的序列,例如a1,a2,a3,a4......an,然后这个序列的美丽值就是socre[a1][a2] + socre[a2][a3] + ..... socre[an-1][an],但是这个序列里面并不是所有的数都是确定的,输入包含一些大于0的数和一些-1,-1表示这个数可以任意,但是要在m的范围内,给出socre[i][j],求这个序列最大的美丽值.
一个二维dp,dp[i][j] 的意义就是当第i个数是j的时候的前i个数的美丽值是dp[i][j],然后递推公式如下:
dp[i][j] = max(dp[i][j],dp[i-1][k] + socre[k][j]);
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 int T,n,m; 8 int value[55][55],note[105],dp[105][55]; 9 int main() 10 { 11 // freopen("in","r",stdin); 12 scanf("%d",&T); 13 while(T--) 14 { 15 scanf("%d%d",&n,&m); 16 for(int i = 1;i <= m;++i) 17 for(int j =1;j <= m;++j) 18 scanf("%d",&value[i][j]); 19 for(int i = 1;i <= n;++i) 20 scanf("%d",¬e[i]); 21 memset(dp,0,sizeof(dp)); 22 for(int i = 2;i <= n;++i) 23 { 24 if(note[i] == -1) 25 { 26 for(int j = 1;j <= m;++j) 27 { 28 if(note[i-1] == -1) 29 for(int k = 1;k <= m;++k) 30 dp[i][j] = max(dp[i][j],dp[i-1][k] + value[k][j]); 31 else dp[i][j] = max(dp[i][j],dp[i-1][note[i-1]] + value[note[i-1]][j]); 32 } 33 } 34 else 35 { 36 if(note[i-1] == -1) 37 for(int k = 1;k <= m;++k) 38 dp[i][note[i]] = max(dp[i][note[i]],dp[i-1][k] + value[k][note[i]]); 39 else dp[i][note[i]] = max(dp[i][note[i]],dp[i-1][note[i-1]] + value[note[i-1]][note[i]]); 40 } 41 } 42 int ans = 0; 43 for(int i = 1;i <= m;++i) 44 ans = max(ans,dp[n][i]); 45 printf("%d ",ans); 46 } 47 return 0; 48 }