题目大意:有一列数据,可以从最上面的开始连接下面相同的元素,然后消除,不过距离不能超过6,询问最后能不能消除完整个数列。
分析:首先讨论一点最远能消除的地方,比如点的位置是x,如若想要消除x+1位置处的值,那么至少也得在x-4处开始消除,所以x后面最多能有4个被消除,也就是最多能下落4个位置,能够消除的最远距离是x+9,不会超过10个状态,所以可以使用状态压缩做,不过有几点还是要注意的,首先输入的数据是从栈底到栈顶的,其次,判断状态的能否达到的时候要注意判断中间有多少个已经被消除的。
代码如下:
======================================================================================================================
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std; const int MAXN = <<;
const int bit = ; int data[MAXN];
bool dp[MAXN][MAXN]; int main()
{
int i, j, k, N; while(scanf("%d", &N) != EOF)
{
memset(data, -, sizeof(data));
memset(dp, , sizeof(dp)); for(i=N; i>; i--)
{
scanf("%d", &data[i]);
} dp[][] = true; for(i=; i<=N; i++)
for(j=; j<MAXN; j++)
{
if(dp[i-][j] == true)
{///这种状态存在
if(j & )
{///本位已经被消除
dp[i][j>>] = true;
}
else
{
int t = ;///纪录已经被消除的,状态1表示被消除,0表示没有 for(k=; k<=bit; k++)
{
if(!(j&(<<k)) && k-t <= &&data[i] == data[i+k])
{///可以消除,两者之间的距离应该不超过6
dp[i][(j>>)|(<<(k-))] = true;
}
else if(j & (<<k))
t++;
}
}
}
} if(dp[N][] == true)
printf("1\n");
else
printf("0\n");
} return ;
}