题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=3632
题意：n个人进行比赛，每个人有一个价值a[i]，最后冠军只有一个，只能相邻两个人进行比赛，输的人被淘汰，问最后冠军价值最大是多少
代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=1e2+5; const int INF=0x3f3f3f3f;int mp[maxn][maxn],w[maxn][maxn]; int a[maxn];int main(){//freopen("in.txt","r",stdin);int T;scanf("%d",&T);for(int t=1; t<=T; t++){int n;scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%d",&a[i]);for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%d",&w[i][j]);for(int i=1; i<=n; i++) w[0][i]=w[n+1][i]=0,w[i][0]=w[i][n+1]=1;memset(mp,0,sizeof(mp));for(int i=0; i<=n+1; i++) mp[i][i+1]=mp[i+1][i]=1; ///构建初始状态i和j能交战 那么mp[i][j]=1;for(int d=2; d<=n+1; d++) ///因为增加了两个虚结点，所以区间的长度至少为3for(int i=0; i+d<=n+1; i++){int j=i+d;for(int k=i+1; k<=j-1; k++)if(mp[i][k] && mp[k][j]){if(w[i][k]) mp[i][j]=1;if(w[j][k]) mp[i][j]=1;}}int ans=-INF;for(int i=1; i<=n; i++)if(mp[0][i] && mp[i][n+1] && a[i]>ans) ans=a[i];printf("Case %d: %d\n",t,ans);}return 0; }