http://acm.hdu.edu.cn/showproblem.php?pid=5074
题意：给你一个的矩阵score[i][j]，然后给你一个数列
，数列中有一些是-1，代表这个数可以换成1~m的任意一个数，然后求
的最大值。
思路：二维dp，dp[i][j]代表i位置的数为j的最大和。 通过前面求和推此位置的最大和，分为四中情况，（a,-1）、（a,b）、（-1，-1）、（-1，b）； dp[i][j]=max(dp[i][j],dp[i-1][k]+g[k][j]);
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 int t,n,m; 7 int g[60][60]; 8 int a[110]; 9 int dp[1000][1000]; 10 11 int main() 12 { 13 scanf("%d",&t); 14 while(t--) 15 { 16 scanf("%d%d",&n,&m); 17 for(int i=1; i<=m; i++) 18 { 19 for(int j=1; j<=m; j++) 20 { 21 scanf("%d",&g[i][j]); 22 } 23 } 24 for(int i=1; i<=n; i++) 25 { 26 scanf("%d",&a[i]); 27 } 28 memset(dp,0,sizeof(dp)); 29 for(int i=2; i<=n; i++) 30 { 31 if(a[i]>0) 32 { 33 if(a[i-1]>0) 34 { 35 dp[i][a[i]]=dp[i-1][a[i-1]]+g[a[i-1]][a[i]]; 36 } 37 else 38 { 39 for(int j=1; j<=m; j++) 40 { 41 dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+g[j][a[i]]); 42 } 43 } 44 } 45 else 46 { 47 for(int j=1; j<=m; j++) 48 { 49 if(a[i-1]>0) 50 { 51 dp[i][j]=max(dp[i][j],dp[i-1][a[i-1]]+g[a[i-1]][j]); 52 } 53 else 54 { 55 for(int k=1; k<=m; k++) 56 { 57 dp[i][j]=max(dp[i][j],dp[i-1][k]+g[k][j]); 58 } 59 } 60 } 61 } 62 } 63 int ans=0; 64 for(int i=1; i<=m; i++) ans=max(ans,dp[n][i]); 65 printf("%d ",ans); 66 } 67 return 0; 68 }