2015
05-23

# LianLianKan

I like playing game with my friend, although sometimes looks pretty naive. Today I invent a new game called LianLianKan. The game is about playing on a number stack.
Now we have a number stack, and we should link and pop the same element pairs from top to bottom. Each time, you can just link the top element with one same-value element. After pop them from stack, all left elements will fall down. Although the game seems to be interesting, it’s really naive indeed.

To prove I am a wisdom among my friend, I add an additional rule to the game: for each top element, it can just link with the same-value element whose distance is less than 6 with it.
Before the game, I want to check whether I have a solution to pop all elements in the stack.

There are multiple test cases.
The first line is an integer N indicating the number of elements in the stack initially. (1 <= N <= 1000)
The next line contains N integer ai indicating the elements from bottom to top. (0 <= ai <= 2,000,000,000)

There are multiple test cases.
The first line is an integer N indicating the number of elements in the stack initially. (1 <= N <= 1000)
The next line contains N integer ai indicating the elements from bottom to top. (0 <= ai <= 2,000,000,000)

2
1 1
3
1 1 1
2
1000000 1

1
0
0

为什么是10个呢，可以想下，从开始的状态最坏的情况是每次栈顶的元素都取最远的，进行5次之后得到的状态是1010101010，未选择的元素恰好为5
总个数为10，所以需要记录栈顶10个元素的状态。

Sure原创，转载请注明出处。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
#define MAX(a , b) ((a) > (b) ? (a) : (b))
using namespace std;
const int maxn = 1300;
int x[maxn],stack[maxn],cnt[maxn];
bool dp[maxn][maxn],vis[maxn][maxn];
int n;

{
memset(cnt,0,sizeof(cnt));
memset(vis,false,sizeof(vis));
for(int i=0;i<n;i++)
{
scanf("%d",&stack[i]);
x[i] = stack[i];
}
return;
}

bool check()
{
if(n & 1) return false;
sort(x , x + n);
int m = x - unique(x , x + n);
for(int i=0;i<n;i++)
{
int idx = lower_bound(x , x + m , stack[i]) - x;
cnt[idx]++;
}
for(int i=0;i<m;i++)
{
if(cnt[i] & 1) return false;
}
return true;
}

bool dfs(int dep , int to , int st)
{
if(vis[dep][st]) return dp[dep][st];
bool flag = false;
int use = 0;
for(int i=dep-1;i>=0 && use < 5;i--)
{
if(st & (1 << (dep - i)))
{
use++;
if(stack[dep] == stack[i])
{
int cur = st;
cur ^= 1;
cur ^= (1 << (dep - i));
if(cur == 0)
{
flag = true;
break;
}
int pos = dep;
while((cur & 1) == 0)
{
cur >>= 1;
pos--;
}
int end = to-1;
while(end >= 0 && pos - end < 10)
{
cur |= (1 << (pos - end));
end--;
}
if(dfs(pos , end+1 , cur))
{
flag = true;
break;
}
}
}
}
vis[dep][st] = true;
return dp[dep][st] = flag;
}

int main()
{
while(~scanf("%d",&n))
{
if(check() == false)
{
puts("0");
continue;
}
puts(dfs(n-1 , MAX(n-10 , 0) , (1 << MIN(10 , n)) - 1) ? "1" : "0");
}
return 0;
}