几道状态压缩DP

节约状态数，排除一些情况：

poj3254 最多12*12的网格，按行递推的话至多有2^12次方的状态数

dp(i,S) = sum( dp(i-1,S') ) 前提是 S与S'不冲突即（S&S'=0）

　　但是这样枚举S和S'就需要 2^24，这样就过大了

　　可以发现，一行中两两不相邻的时候有 S&(S>>1)==0，可以写个程序跑看看总共有几种（377）

　　然后把每一种状态用一个大小为377的数组储存起来

poj1185

dp(i,a,b) = max(dp(i-1,b,c)) + bitcount(a)

a最多有2^10个，递推要用2^30过大

按照上面的方法，假如不讨论上一行的影响，一行中互不攻击的情况应该是(S&(S>>2))==0 && (S&(S>>1))==0

会计算出可行方案只有60

边界的处理:

poj3311

TSP的边界处理要注意：集合中只有一个点的时候是边界

dp[S][v] = min(dp[S-{v}][u]+dist[u][v])

显然S为空的时候没有意义，所以S至少要有一个点

poj1185

　　dp(i,a,b)表示第i行的集合为b，第i-1行集合为a

　　边界条件是dp(0,a,0)，即第-1行为空集，有dp(0,a,0)=bitcount(a)

　　我们令不符合条件的状态为-1，这种技巧很方便

code:

poj1185

/*
ID: neverchanje
PROG:
LANG: C++11
*/
#include<vector>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<queue>
#include<map>
#define INF 0Xfffffffff
#define st_size (1<<18)-1
#define maxn
typedef  long long ll;
using namespace std;

int n,m;
int s[70];
int mat[101];
int dp[2][71][71];
int bitcount[71];

int count(int x){
    int cnt=0;
    while(x>0){    if(x&1) cnt++;    x>>=1; }
    return cnt;
}

int main(){
    freopen("a.txt","r",stdin);
//    freopen(".out","w",stdout);
    cin>>n>>m;
    char w;
    getchar();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
        {
            w=getchar();
            if(w=='H')    mat[i] |= (1<<j);
        }
        getchar();
    }
    
    int cnt=0;
    for(int S=0;S<(1<<m);S++)
        if( (S&(S>>2))==0 && (S&(S>>1))==0 ){
            bitcount[cnt]=count(S); 
            s[cnt++]=S;
        }
    
    memset(dp,-1,sizeof(dp));

    for(int a=0;a<cnt;a++)
        if(!(s[a]&mat[0]))
            dp[0][a][0] = bitcount[a];    
                        
    int i,a,b,c,e;
    for(i=1;i<n;i++){
        e=(i&1);
        for(a=0;a<cnt;a++){
            if(mat[i]&s[a]) continue;
            for(b=0;b<cnt;b++){
                if( (s[a]&s[b]) ) continue;
                for(c=0;c<cnt;c++){
                    if( (s[a]&s[c]) || (dp[e^1][b][c]==-1) ) continue;
                    dp[e][a][b] = max( dp[e^1][b][c]+bitcount[a],dp[e][a][b] ) ;
                }
            }        
        }
    }
    
    int res=0;
    for(a=0;a<cnt;a++)
        for(b=0;b<cnt;b++)
            res = max( dp[(n-1)&1][a][b],res ); 
    cout<<res<<endl;
    return 0;
}

/*
DESCRIPTION:
dp[i][a][b]，a是第i行的集合，b是第i-1行的集合 
第i行的状态与第i-1和i-2行有关，但由于是逐行递推，所以不用包含第i-2行
dp(i,a,b) = max( dp(i-1,b,c) ) + bitcount(a)　 
满足条件的a,b,c有(a&b)==0 且 (b&c)==0  

*/

View Code

poj3311

/*
ID: neverchanje
PROG:
LANG: C++11
*/
#include<vector>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<queue>
#include<map>
#define INF 0Xfffffffff
#define st_size (1<<18)-1
#define maxn
typedef  long long ll;
using namespace std;

int n,m;
int s[70];
int mat[101];
int dp[2][71][71];
int bitcount[71];

int count(int x){
    int cnt=0;
    while(x>0){    if(x&1) cnt++;    x>>=1; }
    return cnt;
}

int main(){
    freopen("a.txt","r",stdin);
//    freopen(".out","w",stdout);
    cin>>n>>m;
    char w;
    getchar();
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
        {
            w=getchar();
            if(w=='H')    mat[i] |= (1<<j);
        }
        getchar();
    }
    
    int cnt=0;
    for(int S=0;S<(1<<m);S++)
        if( (S&(S>>2))==0 && (S&(S>>1))==0 ){
            bitcount[cnt]=count(S); 
            s[cnt++]=S;
        }
    
    memset(dp,-1,sizeof(dp));

    for(int a=0;a<cnt;a++)
        if(!(s[a]&mat[0]))
            dp[0][a][0] = bitcount[a];    
                        
    int i,a,b,c,e;
    for(i=1;i<n;i++){
        e=(i&1);
        for(a=0;a<cnt;a++){
            if(mat[i]&s[a]) continue;
            for(b=0;b<cnt;b++){
                if( (s[a]&s[b]) ) continue;
                for(c=0;c<cnt;c++){
                    if( (s[a]&s[c]) || (dp[e^1][b][c]==-1) ) continue;
                    dp[e][a][b] = max( dp[e^1][b][c]+bitcount[a],dp[e][a][b] ) ;
                }
            }        
        }
    }
    
    int res=0;
    for(a=0;a<cnt;a++)
        for(b=0;b<cnt;b++)
            res = max( dp[(n-1)&1][a][b],res ); 
    cout<<res<<endl;
    return 0;
}

/*
DESCRIPTION:
dp[i][a][b]，a是第i行的集合，b是第i-1行的集合 
第i行的状态与第i-1和i-2行有关，但由于是逐行递推，所以不用包含第i-2行
dp(i,a,b) = max( dp(i-1,b,c) ) + bitcount(a)　 
满足条件的a,b,c有(a&b)==0 且 (b&c)==0  

*/

View Code

poj3254

/*
ID: neverchanje
PROG:
LANG: C++11
*/
#include<vector>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<set>
#include<queue>
#include<map>
#define INF 0Xfffffffff
#define st_size (1<<18)-1
#define MOD  100000000
typedef  long long ll;
using namespace std;

int s[400];
int dp[13][400];

int main(){
//    freopen("a.txt","r",stdin);
//    freopen(".out","w",stdout);
    int n,m,cnt=0;
    cin>>m>>n;
    
    for(int S=0;S<(1<<n);S++)
        if(!(S&(S<<1)))
            s[cnt++] = S;
            
    int mat,x,i,j,k;
    memset(dp,0,sizeof(dp));
    for(i=0;i<m;i++)
    {
        mat=0;
        for(j=0;j<n;j++){ cin>>x; mat |= (x<<j); }
        for(k=0;k<cnt;k++)
        {
            if( (s[k]&mat)!=s[k] ) continue; 
            if(i==0) dp[i][k]=1;
            else{
                for(j=0;j<cnt;j++)
                {
                    if( (s[j]&s[k]) >0)    continue;
                    dp[i][k] = ( dp[i][k] + dp[i-1][j] )%MOD;
                }
            }
        }
    }
    
    int res=0;
    for(k=0;k<cnt;k++)
    {
        if(s[k]&mat<s[k])    continue;
        res= ( res + dp[m-1][k] )%MOD;
    }
    cout<<res<<endl;
    
    return 0;
}

/*
DESCRIPTION:
*/

View Code