这道题就是给你一个序列a， 定义序列的最优美度为d[a[i]][a[i+1]], 现在让sigma(d[a[i]][a[i+1]]) i=1 - n-1最大，当a[i]<0是序列这个位置可以随便选， 否则不能随便选， 则sigma(d[a[i]][a[i+1]]) i=1 - n-1最大是多少？这道题乍一看是搜索， 然而看一下数据范围， 感觉搜索胜任不了， 于是果断想了一种dp的做法，定义dp[i][j]为第i个位置为j时的最大值， 那么答案就可以推出来， 具体见代码：
/************************************************************************* > File Name: 1004.cpp > Author: xingxing > Mail: > Created Time: 2015年12月08日 星期二 19时14分21秒 ************************************************************************/ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int f[100+10][55]; int a[55][55]; int num[105]; int n, m; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i=1; i<=m; i++) for(int j=1; j<=m; j++) scanf("%d", &a[i][j]); memset(f, 0, sizeof(f)); for(int i=1; i<=n; i++) scanf("%d", &num[i]); for(int i=2; i<=n; i++) { if(num[i-1] < 0) { for(int j=1; j<=m; j++) for(int k=1; k<=m; k++) f[i][j] =max(f[i][j], f[i-1][k] + a[k][j]); } else { for(int j=1; j<=m; j++) f[i][j] = max(f[i][j], f[i-1][num[i-1]]+a[num[i-1]][j]); } } int res = 0; if(num[n] < 0) for(int j=1; j<=m; j++) res = max(res, f[n][j]); else res = f[n][num[n]]; printf("%d ", res); } return 0; }