hdu 3632 A Captivating Match(区间dp)

题目链接：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+;

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=; t<=T; t++){

        int n;

        scanf("%d",&n);

        for(int i=; i<=n; i++) scanf("%d",&a[i]);

        for(int i=; i<=n; i++) for(int j=; j<=n; j++) scanf("%d",&w[i][j]);

        for(int i=; i<=n; i++) w[][i]=w[n+][i]=,w[i][]=w[i][n+]=;

        memset(mp,,sizeof(mp));

        for(int i=; i<=n+; i++) mp[i][i+]=mp[i+][i]=; ///构建初始状态i和j能交战 那么mp[i][j]=1;

        for(int d=; d<=n+; d++) ///因为增加了两个虚结点，所以区间的长度至少为3

            for(int i=; i+d<=n+; i++){

                int j=i+d;

                for(int k=i+; k<=j-; k++)

                    if(mp[i][k] && mp[k][j]){

                        if(w[i][k]) mp[i][j]=;

                        if(w[j][k]) mp[i][j]=;

                    }

            }

        int ans=-INF;

        for(int i=; i<=n; i++)

            if(mp[][i] && mp[i][n+] && a[i]>ans) ans=a[i];

        printf("Case %d: %d\n",t,ans);

    }

    return ;

}