关于状态压缩的学习

 方格取数（1）

Problem - 1565

思路：用二进制来表示每一行取或不取的状态，总共有20行，也就是2的20次方（1048576）

先在这1048576种状态下筛出每行之间不相邻的状态，也就是i&(i>>1)==0就是合法的状态。

之后把筛出来合法的状态，不超过2e4。

遍历每一行，假设一行的的状态是j，那么假设上一行是k，判定tot[j]&tot[k]==0时,取dp[i][j]=max(dp[i][j],dp[i-1][k]+va);

最后取 for(int i=1;i<=tt;i++)ma=max(ma,dp[n][i]);

代码：

#include
using namespace std;
int n,m;int mp[30][30];
int dp[25][20000];int tot[20000];
int fin(int x,int y){
     int sum=0;int t=1;
     while(y){
          if(y&1){
               sum+=mp[x][t];
          }
          y=y>>1;
          t++;
     }
     return sum;
}
void solve(int n){
     int tt=0;
     memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>mp[i][j];
     for(int i=0;i<(1<
          if((i&(i>>1))==0){tot[++tt]=i;}//每一列的状况 少于2e4
     }
     for(int i=1;i<=n;i++){
          for(int j=1;j<=tt;j++){
               int va=fin(i,tot[j]);//如果当前的j的状态
               for(int k=1;k<=tt;k++){
                    if((tot[j]&tot[k])==0)
                         dp[i][j]=max(dp[i][j],dp[i-1][k]+va);
               }
          }
     }
     int ma=0;
     for(int i=1;i<=tt;i++)ma=max(ma,dp[n][i]);
     cout<'\n';
}
signed main()
{
     int n;while(cin>>n){solve(n);}
     return 0;
}

蒙德里安的梦想 

2411 -- Mondriaan's Dream

思路：参考poj2411 棋盘覆盖

设横着放的是11，竖着放是01，如果当前是【i，j】

情况一：【i-1，j】是0，那么【i，j】是1（这是一定的）

情况二：【i-1，j】是1，那么【i，j】为0

情况三：【i-1，j】是1，那么【i，j】为1

但是如果按照以上的情况，那么

01

11

这样的情况则是不符合要求的

对于情况二来说是没有问题的，但对于情况三就不行（如上面的例子）

11

00

11（情况二）

所以第三种情况改为

第 i-1 行第 j-1 ，j 列都为1，第 i 行第 j-1，j列都为1。

 知道了大致思想，那么就可以开始做了。

设dp【200005】【20】，其中左边的为一行的状态，右边为行数

首先先把0到(1<

但如果出现010这样的数字是不符合规范的，所以这样的数字就不需要了

于是初始化就完成了。

接着根据上面的三个条件，开始根据上一行r-1的条件，推出下一行r的条件，最后每一列都推完，那么当前的状态scur的方案数就要加上dp[s][r-1]

最后因为最后一行都填满了，所以最后一行都是1，所以就输出dp[(1<

代码

#include
using namespace std;
long long dp[200005][22];
int n,m;
bool check(int x){
     while(x){
          if((x&1)&&(x&2))x>>=2;
          else if((x&1)==0)x=x>>1;
          else return false;
     }
     return 1;
}
void dfs(int r,int c,int s,int scur){ //搜索r-1行状态s可以r行匹配的所有状态scur
    if(c>m) return;
    if(c==m) {
          dp[scur][r]+=dp[s][r-1];
          return;
    }
    if(s>>c&1){
        dfs(r,c+1,s,scur); //1->0
        if(s>>c&2)
            dfs(r,c+2,s,scur|3<//11->11
    }
    else dfs(r,c+1,s,scur|1<//0->1
}
int main()
{
    while(cin>>n>>m,n){
        if(n*m&1) {puts("0");continue;}
        if(m>n)swap(m,n);
        memset(dp,0,sizeof dp);
        for(int i=0;i<(1<
            if(check(i))dp[i][0]=1;
        for(int i=1;i
            for(int j=0;j<(1<
                dfs(i,0,j,0);
          cout<1<-1][n-1]<
     }
     return 0;
}

91. 最短Hamilton路径

91. 最短Hamilton路径 - AcWing题库 

思路：

最终的结束状态是status=（1<

 状态转移的思想是

当前状态是i，我要到 j 这个点，那么我要从已经走过的路中选一个已经走过的点，然后取最小值

每个状态是从0到（1<

代码

#include
using namespace std;
int mp[25][25];
long long f[(1<<20)][25];
int main()
{
     memset(f, 0x3f, sizeof(f));
     int n;cin>>n;
     for(int i=0;ifor(int j=0;j>mp[i][j];
     f[1][0]=0;
     for(int i=0;i<(1<
          for(int j=0;j
               if(i&(1<//代表当前状态是有j的
                    for(int k=0;k<=n;k++){
                         if(k==j)continue;
                         if(i&(1<//如果有k的话
                              f[i][j]=min(f[i][j],f[i-(1<
                         }
                    }
               }
          }
     }
     cout<1<-1][n-1];
     return 0;
}

P1896 [SCOI2005] 互不侵犯

P1896 [SCOI2005] 互不侵犯 - 洛谷