bzoj1088 扫雷

Description

　　相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。

Input

　　第一行为N，第二行有N个数，依次为第二列的格子中的数。（1<= N <= 10000）

Output

　　一个数，即第一列中雷的摆放方案数。

Sample Input

2 1 1

Sample Output

2   这道题是装压DP，dp[i][k][j]代表，当前第i个格，j是他上面左中右三个的状态，k是他前面一个，也就是i-1的上面三个状态。 转移方程就是dp[i][k][j]+=dp[i-1][j][l](在k、j、l合法的情况下） 还有一个要注意的就是判断合法，具体看代码，但是一定要特殊处理当i=1或i=n 这道题类似于poj1185炮兵列阵，都是处理前两行影响当前的状压DP。 #include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read(); #define MAXN 20010 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return f*x; } int a[MAXN],dp[MAXN][8][8],n; inline bool check(int ind,int j){ int i=a[ind]; if(ind==n){ if(i==0){ if(j==0) return 1; return 0; } if(i==1){ if(j==2 || j==4) return 1; return 0; } if(i==2){ if(j==6) return 1; return 0; } if(i==3) return 0; } if(ind==1){ if(i==0){ if(j==0) return 1; return 0; } if(i==1){ if(j==1 || j==2) return 1; return 0; } if(i==2){ if(j==3) return 1; return 0; } if(i==3) return 0; } if(i==0){ if(j==0) return 1; return 0; } if(i==1){ if(j==1 || j==2 || j==4) return 1; return 0; } if(i==2){ if(j==3 || j==5 || j==6) return 1; return 0; } if(i==3){ if(j==7) return 1; return 0; } } inline bool is1(int i,int j){ i=i&3; j=j&6; j=j>>1; if(i==j) return 1; return 0; } inline bool is2(int i,int j){ i=i&1; j=j&4; j=j>>2; if(i==j) return 1; return 0; } int main(){ // freopen("1.txt","r",stdin); in(n); REP(i,1,n) in(a[i]); if(n==1){ if(a[1]==0 || a[1]==1) cout<<1; else cout<<0; return 0; } REP(i,0,7) REP(j,0,7) if(check(1,i) && check(2,j) && is1(i,j)) dp[2][i][j]=1; REP(i,3,n) REP(j,0,7) if(check(i,j)) REP(k,0,7) if(check(i-1,k)) REP(l,0,7) if(check(i-2,l) && is1(k,j) && is1(l,k) && is2(l,j)){ // if(dp[i-1][l][k]) cout<<l<<" "<<k<<" "<<j<<endl; dp[i][k][j]+=dp[i-1][l][k]; } int ans=0; REP(i,0,7) REP(j,0,7) ans+=dp[n][i][j]; cout<<ans; return 0; }

 

转载于:https://www.cnblogs.com/jason2003/p/9714786.html

相关资源：JAVA上百实例源码以及开源项目