首页 > ACM题库 > HDU-杭电 > HDU 3833-YY’s new problem-递推-[解题报告]HOJ
2015
04-13

HDU 3833-YY’s new problem-递推-[解题报告]HOJ

YY’s new problem

问题描述 :

Given a permutation P of 1 to N, YY wants to know whether there exists such three elements P[i1], P[i2], P[i3] that
P[i1]-P[i2]=P[i2]-P[i3], 1<=i1<i2<i3<=N.

输入:

The first line is T(T<=60), representing the total test cases.
Each test case comes two lines, the former one is N, 3<=N<=10000, the latter is a permutation of 1 to N.

输出:

The first line is T(T<=60), representing the total test cases.
Each test case comes two lines, the former one is N, 3<=N<=10000, the latter is a permutation of 1 to N.

样例输入:

2
3
1 3 2
4
3 2 4 1

样例输出:

N
Y

/*
分析:
    巨汗- -III……
    3000MS暴力水过。。。
    应该可以用类似dp一样的递推来大量优化的,
不过暂时牟想出来。

    谁有好方法欢迎讨论0.0

                        2012-08-01 16:37
*/

#include"stdio.h"
#include"string.h"


int main()
{
	int T;
	int n;
	int i,l;
	int t;
	int num[10011];
	int hash[10011];
	int flag;
	int temp;


	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(hash,0,sizeof(hash));
		for(i=0;i<n;i++)
		{
			scanf("%d",&num[i]);
			hash[num[i]]=i;
		}


		flag=0;
		t=n/2;
		for(i=1;i<t;i++)
		{
			if(flag)	break;
			temp=num[i]*2;
			for(l=0;l<i;l++)
			{
				if(num[l]>=temp)	continue;
				if(temp-num[l]>n)	continue;
				if(hash[temp-num[l]]>i)	{flag=1;break;}
			}
		}


		t=n-1;
		for(i=n/2;i<t;i++)
		{
			if(flag)	break;
			temp=num[i]*2;
			for(l=i+1;l<n;l++)
			{
				if(num[l]>=temp)	continue;
				if(temp-num[l]>n)	continue;
				if(hash[temp-num[l]]<i)	{flag=1;break;}
			}
		}


		if(flag)	printf("Y\n");
		else		printf("N\n");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/7819102


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

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