首页 > ACM题库 > HDU-杭电 > HDU 3632-A Captivating Match[解题报告]HOJ
2014
11-29

HDU 3632-A Captivating Match[解题报告]HOJ

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
    会陷入死循环

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。

  4. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”