hdu3632 A Captivating Match--区间dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=3632​​

题意：n个人比赛，每个人一个价值v[i]，相邻两人a，b比赛，输的人淘汰，最后剩下的那个人的价值最大可以是多少？

分析：相邻比赛，最后剩下的人可以有好几种，但是这好几种中我们要选一个价值最大的。起先的思路是枚举最大的价值（依次变小），看从他开始是否可以把所有人淘汰，这个思路是不对的，因为题意 是相邻才可以比赛，最终参考大神的代码，，好思路啊。

dp[i][j]表示第i和j人可以相邻，n个人标号1到n，我们再设置0和n+1，如果n个人中假设k是最后剩下的，那么dp[0][k]等于dp[k][n+1]的。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#define INF 99999999
#define eps 0.0001
using namespace std;

int t;
int n;
int v[105];
int a[105][105];
int dp[105][105];

int main()
{
  scanf("%d", &t);

  for (int cas = 1; cas <= t; cas++)
  {
    memset(dp, 0, sizeof(dp));
    memset(a, 0, sizeof(a));

    scanf("%d", &n);

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

    

    for (int i = 1; i <= n; i++)
    {
      a[0][i] = a[n + 1][i] = 0;
      a[i][0] = a[i][n + 1] = 1;
    }
    for (int i = 0; i <= n; i++)
    {
      dp[i][i] = 1;
      dp[i][i + 1] = 1;
    }
    dp[n + 1][n + 1] = 1;

    for (int l = 2; l <= n; l++)
    {
      for (int i = 0; i + l <= n + 1; i++)
      {
        int j = i + l;
        for (int k = i; k <= j; k++)
        {
          if (dp[i][k] && dp[k][j] && (a[i][k] || a[j][k]))
            dp[i][j] = 1;
        }
      }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
      if (dp[0][i] && dp[i][n + 1])
        ans = max(ans, v[i]);

    printf("Case %d: %d\n", cas, ans);
  }
  return 0;
}