题意：给定一个序列 有些位数未知，给你如果两个数连续所得到的能量，问你怎么安排数字使得总能量最大
解题思路：dp，只与上一个字母有关。
解题代码：
1 // File Name: e.cpp 2 // Author: darkdream 3 // Created Time: 2014年10月22日 星期三 12时16分10秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 int dp[200][60]; 28 int mp[60][60]; 29 int main(){ 30 int t; 31 scanf("%d",&t); 32 while(t--) 33 { 34 memset(mp,0,sizeof(mp)); 35 memset(dp,-1,sizeof(dp)); 36 int n , m ; 37 scanf("%d %d",&n,&m); 38 for(int i = 1;i <= m;i ++ ) 39 for(int j = 1;j <= m ;j ++) 40 scanf("%d",&mp[i][j]); 41 int t; 42 scanf("%d",&t); 43 dp[1][t] = 0 ; 44 if(t == -1) 45 for(int i = 1;i <= m;i ++) 46 dp[1][i] = 0 ; 47 for(int i = 2;i <= n;i ++) 48 { 49 scanf("%d",&t); 50 if(t == -1) 51 { 52 for(int j = 1; j <= m ;j ++) 53 { 54 if(dp[i-1][j] != -1) 55 for(int s = 1;s <= m ;s ++) 56 dp[i][s] = max(dp[i][s],dp[i-1][j] + mp[j][s]); 57 } 58 }else { 59 for(int s = 1; s <= m; s ++) 60 { 61 if(dp[i-1][s] != -1) 62 dp[i][t] = max(dp[i][t],dp[i-1][s] + mp[s][t]); 63 } 64 } 65 //for(int j = 1;j <= m;j ++) 66 } 67 int mx = -1; 68 for(int i = 1;i <= m;i ++) 69 if(dp[n][i] > mx) 70 mx = dp[n][i]; 71 printf("%d ",mx); 72 73 } 74 return 0; 75 }