2014
11-29

# A Captivating Match

The FIFA 2010 Soccer World Cup has gone, Small Jan returned to her own planet. After she saw the Spain emerged the biggest winner, she believe that, as a Queen, she can also arrange a captivating match-International Cavalry PK Contest(ACM-ICPC) for her lovely and hard working subjects. But her subjects are so busying that they have no time to watch the group match. So, our smart Queen wants to make the final more valuable. Every Knight has a value in people’s minds and the final’s value is dependent on the last valiancy Knights (equals to the winner’s value).
Now assuming that the Knights have been numbered from 1 to N, and any time Small Jan could arrange a match between any two Knights adjacent to each other, but the loser will quit. For example, (1, 2, 3, 4, 5),if the Queen arranged Knights 3 and 4 for a match and Knight 3 lost, then Knights 2 and 4 would be adjacent to each other (the result of each Knight competing with others is saved in a table).
Here, Small Jan want to know the max value of the final, can you help her?

The first line of the input is a single positive integer T(0 < T <= 30), telling the number of test scenarios to follow.
Each scenario begins with a line containing an integer N, 0 < N <= 100, being the number of Knights.
The following line contains N integers, 0 < Vi < 1000, being the value of each Knight in people’s minds.
Thelast is a N × N matrix. If a[i,j] = 1 indicate when Knight i competing with j, Knight i always win, which also means a[j, i] must equals 0 and if i=j, a[i,j] must equals 0.

The first line of the input is a single positive integer T(0 < T <= 30), telling the number of test scenarios to follow.
Each scenario begins with a line containing an integer N, 0 < N <= 100, being the number of Knights.
The following line contains N integers, 0 < Vi < 1000, being the value of each Knight in people’s minds.
Thelast is a N × N matrix. If a[i,j] = 1 indicate when Knight i competing with j, Knight i always win, which also means a[j, i] must equals 0 and if i=j, a[i,j] must equals 0.

2
3
1 2 3
0 1 0
0 0 1
1 0 0
3
1 2 3
0 1 1
0 0 0
0 1 0

Case 1: 3
Case 2: 1

/* ***********************************************
Author        :kuangbin
Created Time  :2013-11-19 19:43:32
File Name     :E:\2013ACM\比赛练习\2013-11-19\A.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;

const int MAXN = 110;
int a[MAXN];
int g[MAXN][MAXN];
bool dp[MAXN][MAXN];

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = 0;
int n;
scanf("%d",&T);
while(T--)
{
iCase++;
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",&g[i][j]);
memset(dp,false,sizeof(dp));
for(int i = 1;i <= n;i++)
{
if(i > 1 && g[i-1][i])
dp[i][i] = true;
if(i < n && g[i+1][i])
dp[i][i] = true;
}
for(int i = 1;i <= n+1;i++)
for(int j = 0;j < i;j++)
dp[i][j] = true;
/*
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
printf("%d ",dp[i][j]);
cout<<endl;
}
*/
for(int i = n;i >= 1;i--)
for(int j = i + 1;j <= n;j++)
{
for(int k = i;k <= j;k++)
if(dp[i][k-1] && dp[k+1][j])
{
if((i > 1 && g[i-1][k]) || (j < n && g[j+1][k]))
{
dp[i][j] = true;
break;
}
}
if(!dp[i][j])
{
bool flag = true;
if(i > 1)
{
for(int k = i;k <= j;k++)
if(g[i-1][k] == 0)
{
flag = false;
break;
}
if(flag)dp[i][j] = true;
}
if(j < n)
{
flag = true;
for(int k = i;k <= j;k++)
if(g[j+1][k] == 0)
{
flag = false;
break;
}
if(flag)dp[i][j] = true;
}
}
}
/*
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
printf("%d ",dp[i][j]);
cout<<endl;
}
*/
int ans = 0;
for(int i = 1;i <= n;i++)
if(dp[1][i-1] && dp[i+1][n])
ans = max(ans,a[i]);
printf("Case %d: %d\n",iCase,ans);
}
return 0;
}

1. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环