题意:长度为n(n<=1000)的栈,栈顶元素可以与下面1~5个数中相同的元素消去,问最后能都完全消去。
题解:dp[i][j]表示当前栈顶10个元素的状态为 i 栈顶深度为 j 时是否可行(1代表当前元素未选,0代表已选),转移很直观但dp方程不好写,记忆化dfs实现。
为什么是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; void read() { 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)) { read(); if(check() == false) { puts("0"); continue; } puts(dfs(n-1 , MAX(n-10 , 0) , (1 << MIN(10 , n)) - 1) ? "1" : "0"); } return 0; }