题干：
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.
Input
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)
Output
For each test case, output “1” if I can pop all elements; otherwise output “0”.
Sample Input
2
1 1
3
1 1 1
2
1000000 1 Sample Output
1
0
0 题目大意：
给你有n个数的栈，连续的6个数中有两个一样的数可以消除，一次只能消除两个，且最头上那个必须被选择（也就是每次必须从头上开始选），问最终这个栈的数能不能被消完。
解题报告：
刚开始贪心最近的，发现不行，因为可能要消远的 因为可能别人需要用这个来减少距离。后来尝试贪心最远的，，都WA了，看来只能dfs了、、
错误代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[1005];
int main()
{
int n;
while(~scanf("%d",&n)) {
vector<ll> vv;
for(int i = 1; i<=n; i++) {
scanf("%lld",&a[i]);
}
for(int i = n; i>=1; i--) {
vv.push_back(a[i]);
}
if(n%2 == 1) {
printf("0\n");continue;
}
vector<ll> :: iterator it;
int flag = 0;
while(1) {
it = vv.begin();
flag = 0;
for(int i = 1; i<=5; i++) {
if( ( it+i ) == vv.end()) {
flag=0;break;
}
if(*(it+i) == (*it)) {
flag=1;vv.erase(it+i);vv.erase(it);break;
}
}
if(flag == 0) break;
if(vv.size() == 0) break;
}
if(vv.size()) printf("0\n");
else printf("1\n");
}
return 0 ;
} AC代码：（丑陋的搜索）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
bool vis[MAX];
int flag,n;
void dfs(int cur) {
while(cur <= n && vis[cur]) cur++;
if(cur > n) {//已经说明vis[n]=1了所以不用判断了
flag = 1;
return ;
}
//if(cur == n) return;//因为已经判断奇偶了，所以这一步也不需要了
if(flag) return;
vis[cur]=1;
int cnt = 0;
int j=cur+1;
for(; cnt<=5;) {
if(j>=n+1) return;
if(vis[j]) {
j++;
continue;
}
//if(cur+i>n) return;
if(a[j] == a[cur]) {
vis[j]=1;
dfs(cur+1);
vis[j]=0;
}
cnt++;
j++;
if(flag) return;
}
vis[cur]=0;
}
map<ll,int>mp;
int main() {
while(~scanf("%d",&n)) {
flag = 0;
mp.clear();
for(int i = n; i>=1; i--) {
scanf("%lld",&a[i]);
vis[i]=0;
mp[a[i]]++;
}
if(n%2 == 1 ) {
printf("0\n");
continue;
}
map<ll,int>::iterator it;
for(it=mp.begin(); it!=mp.end(); it++) {
if((it->second)%2==1) {
flag = 2;
break;
}
}
if(flag == 2) {
puts("0");
continue;
}
dfs(1);
if(flag) puts("1");
else puts("0");
}
return 0 ;
} AC代码3：（把dfs中while那一部分给改了）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
bool vis[MAX];
int flag,n;
void dfs(int cur) {
if(cur > n) {
flag = 1;return;
}
if(vis[cur]) {
dfs(cur+1); return;
}
if(flag) return;
vis[cur]=1;
int cnt = 0;
int j=cur+1;
for(; cnt<=5;) {
if(j>=n+1) return;
if(vis[j]) {
j++;
continue;
}
//if(cur+i>n) return;
if(a[j] == a[cur]) {
vis[j]=1;
dfs(cur+1);
vis[j]=0;
}
cnt++;
j++;
if(flag) return;
}
vis[cur]=0;
}
map<ll,int>mp;
int main() {
while(~scanf("%d",&n)) {
flag = 0;
mp.clear();
for(int i = n; i>=1; i--) {
scanf("%lld",&a[i]);
vis[i]=0;
mp[a[i]]++;
}
if(n%2 == 1 ) {
printf("0\n");
continue;
}
map<ll,int>::iterator it;
for(it=mp.begin(); it!=mp.end(); it++) {
if((it->second)%2==1) {
flag = 2;
break;
}
}
if(flag == 2) {
puts("0");
continue;
}
dfs(1);
if(flag) puts("1");
else puts("0");
}
return 0 ;
} 去掉map：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
bool vis[MAX];
int flag,n;
ll fk;
void dfs(int cur) {
if(cur > n) {
flag = 1;
return;
}
if(vis[cur]) {
dfs(cur+1);
return;
}
if(flag) return;
vis[cur]=1;
int cnt = 0;
int j=cur+1;
for(; cnt<=5;) {
if(j>=n+1) return;
if(vis[j]) {
j++;
continue;
}
//if(cur+i>n) return;
if(a[j] == a[cur]) {
vis[j]=1;
dfs(cur+1);
vis[j]=0;
}
cnt++;
j++;
if(flag) return;
}
vis[cur]=0;
}
map<ll,int>mp;
int main() {
while(~scanf("%d",&n)) {
flag = 0;
mp.clear();
for(int i = n; i>=1; i--) {
scanf("%lld",&a[i]);
vis[i]=0;
fk ^= a[i];
}
if(n%2 == 1 || fk != 0 ) {
printf("0\n");
continue;
}
dfs(1);
if(flag) puts("1");
else puts("0");
}
return 0 ;
} 比较美观的版本：（AC代码）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
ll a[MAX];
bool vis[MAX];
int flag,n;
void dfs(int cur) {
if(cur > n) {
flag = 1; return;
}
if(vis[cur]) {
dfs(cur+1); return;
}
vis[cur]=1;
int cnt = 0;
int now=cur+1;
for(; cnt<=5;) {
if(now>n) return;
if(vis[now]) {
now++;
continue;
}
if(a[now] == a[cur]) {
vis[now]=1;
dfs(cur+1);
vis[now]=0;
}
cnt++; now++;
if(flag) return;
}
vis[cur]=0;
}
int main() {
while(~scanf("%d",&n)) {
flag = 0;
for(int i = n; i>=1; i--) {
scanf("%lld",&a[i]);
vis[i]=0;
}
if(n%2 == 1 ) {
printf("0\n");
continue;
}
dfs(1);
if(flag) puts("1");
else puts("0");
}
return 0 ;
} 总结：
刚开始一直dfs的是TLE或者是WA，，仔细原因就不深究了（太麻烦了），但是代码确实有一个地方写的有问题，首先刚开始dfs是这么实现的。。。
void dfs(int cur) {
while(cur <= n && vis[cur]) cur++;
if(cur > n && vis[n]) {
flag = 1;
return ;
}
if(cur > n) return;
if(vis[cur]) {
dfs(cur+1);
return;
}
if(flag) return;
vis[cur]=1;
for(int i = 1; i<=5; i++) {
if(vis[cur+i]) continue;
if(a[cur+i] == a[cur]) {
vis[cur+i]=1;
dfs(cur+1);
vis[cur+i]=0;
}
if(flag) return;
}
vis[cur]=0;
} 这就显然有问题了，，（不保证是原始版本了反正我随便挑了个WA的代码就放上来了），主要就是在于for(int i = 1; i<=5; i++)这里就不对，，因为没有考虑到中间有的数字可能已经被使用过了、题目中说的连续5个数字，，不是真正的物理连续，而是消除之后剩下的数字的连续的五个，所以不能这么写代码、并且还有小错误不断：经常把a[cur]写成a[i]了。。
还有一个地方，主函数中判断每个数出现次数是否是偶数次，经检验，这个剪枝就算不加，也不会TLE。。。
方法2：（状压dp）
看了别人的代码发现还有一种神奇的状压dp方法。
首先讨论一点最远能消除的地方，比如点的位置是x，如若想要消除x+1位置处的值，那么至少也得在x-4处开始消除，所以x后面最多能有4个被消除，也就是最多能下落4个位置，能够消除的最远距离是x+9，不会超过10个状态。
我们用dp[i][j]代表到第i个元素，且包含他和后面的十个元素状态为j时，这个是否合法。其中状态j：如果某一位为1，代表已经消除，某一位为0，代表没有消除。
那个t的作用是：判断状态的能否达到的时候要注意判断中间有多少个已经被消除的。
//状压dp
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int MAXN = 1<<10;
const int bit = 9;
int data[MAXN];
bool dp[MAXN][MAXN];
int main()
{
int i, j, k, N;
while(scanf("%d", &N) != EOF)
{
memset(data, -1, sizeof(data));
memset(dp, 0, sizeof(dp));
for(i=N; i>0; i--)
{
scanf("%d", &data[i]);
}
dp[0][0] = true;
for(i=1; i<=N; i++)
for(j=0; j<MAXN; j++)
{
if(dp[i-1][j] == true)
{///这种状态存在
if(j & 1)
{///本位已经被消除
dp[i][j>>1] = true;
}
else
{
int t = 0;///纪录已经被消除的，状态1表示被消除，0表示没有
for(k=1; k<=bit; k++)
{
if(!(j&(1<<k)) && k-t <=5 &&data[i] == data[i+k])
{///可以消除,两者之间的距离应该不超过6
dp[i][(j>>1)|(1<<(k-1))] = true;
}
else if(j & (1<<k))
t++;
}
}
}
}
if(dp[N][0] == true)
printf("1\n");
else
printf("0\n");
}
return 0;
}
京公网安备 11010502036488号