2015
04-13

# 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;
}

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];
会报错 提示表达式必须含有常量值。该怎么修改呢。。