题意:有一个n*n的棋盘,要在上面放将,一个将可以控制本身的位置和上下左右四格,棋盘上有一些地方不能放将,但是这些点也要被控制,问最少要放几个将。
思路:状态压缩DP,我们反过来想,最多空多少格不放,能控制所有的格子。
对于数据,我们先做一个预处理,求出每行可以的状态和这个状态对应空的格数,这里我用f[i][j]表示第i行在j状态下空的格数,如果j状态不可以则赋值-1。之后我也求出一个每种状态的控制范围,用ff[j]表示j状态下这一行控制的情况。
这些做完后就是一个DP的过程,对于第i行的控制情况,和第i-1行的放置情况有关系,当然,这里第一行除外,同时第i行一定要确保第i-1行未被控制的格子能控制到,第i行和i-1行在同一列不可能都有放置,等等一系列情况考虑之后,可以用下面的状态转移方程:
dp[i][j][ff[j]|k]=max(dp[i][j][ff[j]|k],dp[i-1][k][l]+f[i][j]);
这里i代表第i行,j代表第i行的放置状态,k代表第i-1行的放置状态,ff[j]|k 即为第i行的控制状态,l为第i-1行控制状态。
处理完所有行后,看最后一行全被控制的状态,取最大值。然后将格子数减它就能得到答案了,不可能的情况酌情判断。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> #include<vector> #include<queue> #include<cmath> using namespace std; int m,n; bool h[11][11]; int f[11][555]; int ff[555]; int dp[11][555][555]; void pre() { int u=(1<<n); for(int i=0;i<n;i++) { for(int j=0;j<u;j++) { int cnt=0,num=0,r=j; bool ok=0; for(int k=n-1;k>=0;k--) { if(r%2) { if(h[i][k]) { ok=1; break; } if(cnt) { ok=1; break; } cnt=1; } else { num++; cnt=0; } r/=2; } if(ok)f[i][j]=-1; else { f[i][j]=num; } } } for(int i=0;i<u;i++) { int r=i; int t=0; if(r%2)t=(t|(1<<1)); r/=2; for(int k=n-2;k>0;k--) { if(r%2)t=(t|((1<<(n-k))+(1<<(n-k-2)))); r/=2; } if(r%2)t=(t|(1<<(n-2))); t=(t|i); ff[i]=t; } } int main() { int x,y; while(scanf("%d%d",&n,&m)!=EOF) { memset(h,0,sizeof(h)); for(int i=0;i<m;i++) { scanf("%d%d",&x,&y); h[x-1][y-1]=1; } if(n==1) { if(h[0][0])cout<<-1<<endl; else cout<<1<<endl; continue; } pre(); int u=(1<<n); memset(dp,-1,sizeof(dp)); for(int i=0;i<u;i++) { if(f[0][i]!=-1) { dp[0][i][ff[i]]=f[0][i]; } } for(int i=1;i<n;i++) { for(int j=0;j<u;j++) { if(f[i][j]==-1)continue; for(int k=0;k<u;k++) { if(j&k)continue; if(f[i-1][k]==-1)continue; for(int l=k;l<u;l++) { if(dp[i-1][k][l]==-1)continue; if((ff[k]&l)!=ff[k])continue; if((j|l)!=u-1)continue; dp[i][j][ff[j]|k]=max(dp[i][j][ff[j]|k],dp[i-1][k][l]+f[i][j]); } } } } int ans=0; for(int i=0;i<u;i++)ans=max(ans,dp[n-1][i][u-1]); if(ans)cout<<n*n-ans<<endl; else cout<<-1<<endl; } return 0; }