状态压缩dp

状压dp

用于对所有状态进行枚举并且向后更新，但因为状态压缩，不能用于数量较大的情况

J - TravellingHDU - 3001

题意：给一幅双向路径权值图，可以任意起点，并且每个点最多可以经过2次，求经过所有点所花费费用最少。

3进制状态压缩dp

dp[state][j],state 为3进制，记录一个点经过次数。j表示尾点。

遍历j的边，找下一个点K，

先决条件：1) state中K的经过数小于2 2) dp[state][j] + path[j][k] < dp[state + three[K]][K] (这里维护最短)

dp[state + three[K]][K] = dp[state][j] + path[j][k];

https://www.cnblogs.com/BugClearlove/p/13686911.html

Corn Fields POJ - 3254

题意：给一块地，地上有地方不可种树，牛不喜欢吃东西四周有其他牛，所以种树必须四周都没树。

对每一行状态压缩，通过前一行状态种树情况判断下一行的选择，并且前一列种玉米会导致下一列无法种植，并且土地也要适合种树才行。

首先3循环吧，第一循环：一行行下来；第二循环：一行所有状态；第三循环：一列列来，因为dp数组用二维没有记录列情况；所以，这里用dfs一列到底。

dp[0][0] =1 ;这里求得是方案数，如果第一行可行则肯定从第0行所得，所以万物之始为1。

dp[i][state], dfs(i,j,state,next,flag); flag为前一列是否种树

dp[i+1][next] += dp[i][state]; next 由state通过dfs和决策进行迭代求得，存在即合理。

（这里注意，行是从1开始，列是从0开始，因为列要配合2进制状态）

#include <iostream>
#include <cstring>

using namespace std;

const int INF = 2e9;
const int MOD = 100000000;

int dp[13][1<<13];
int ans,n,m,ditu[13][13];

void init(){
    memset(ditu,0,sizeof ditu);
    memset(dp,0,sizeof dp);
    dp[0][0] = 1;//万物之始为1
    ans = 0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=0;j<m;j++) cin>>ditu[i][j];
}
//flag：前一列是否种玉米
void dfs(int x,int y,int state,int next,bool flag){
    if(y==m) { dp[x+1][next]=(dp[x+1][next]+dp[x][state])%MOD; return ;}
    if(!flag&&!(state&(1<<y))&&ditu[x+1][y]) dfs(x,y+1,state,next|(1<<y),true);
    dfs(x,y+1,state,next,false);
}

void solve(){
    for(int i=0;i<n;i++) for(int j=0;j<(1<<m);j++) if(dp[i][j]>0) dfs(i,0,j,0,false);
    for(int i=0;i<(1<<m);i++) ans = (ans+dp[n][i])%MOD;
    cout<<ans<<endl;
}

int main()
{
    init();solve();
    return 0;
}

View Code

Mondriaan's DreamPOJ - 2411

题意：给一个方块空间，然后需要用长为2宽为1的小方块填充，问填满的方式种数。

3循环：1列列，然后状态，再然后1行行

决策：插入横砖，则影响下一行。竖砖需要判断连续两个0。

dp[j][state] ：j为第j列；这里state并不是每一行的决策状态，而是前一列导致后一列还没开始决策就遇到的状态。即状态中的1：代表前一列同一行插入一个横砖块导致后一列这一行不能做任何操作。

#include <iostream>
#include <cstring>

using namespace std;

int n,m;
long long dp[13][1<<12];//dp[j][state] 影响第j列的state的数量。这里state并不是每一行的决策，
//而是前一列导致后一列还没开始决策就遇到的状态。1代表前一列插入一个横砖块导致后一列这一行不能做操作

void init(){
    memset(dp,0,sizeof dp);
    dp[1][0] = 1;
    //if(n>m) n=n^m,m=n^m,n=n^m;
}

void dfs(int x,int y,int state,int next){
    if(x==n) {dp[y+1][next] += dp[y][state];return ;}
    if(state&(1<<x)) dfs(x+1,y,state,next);
    else{
        dfs(x+1,y,state,next|1<<x);
        if(x+1<n&&!(state&(1<<x+1))) dfs(x+2,y,state,next);
    }
}

void solve(){
    //这里先一列列，然后一列列状态遍历，然后一行行决策
    for(int i=1;i<=m;i++) for(int j=0;j<(1<<n);j++) if(dp[i][j]>0) dfs(0,i,j,0);
    cout<<dp[m+1][0]<<endl;
}

int main()
{
    while(cin>>n>>m&&n&&m) {init();solve();}
    return 0;
}

View Code

dp[j][state] :j为第j列；这里state是每一行的决策状态;即状态中的1：代表这一列这一行插入一个横砖。

#include <iostream>
#include <cstring>

using namespace std;

int n,m;
long long dp[12][1<<12];

void init(){
    memset(dp,0,sizeof dp);
    dp[0][0] = 1;
}

void dfs(int x,int y,int state,int next){
    if(x==n) {dp[y+1][next] += dp[y][state];return ;}
    if(state&(1<<x)) dfs(x+1,y,state,next);
    else{
        dfs(x+1,y,state,next|1<<x);
        if(x+1<n&&!(state&(1<<x+1))) dfs(x+2,y,state,next);
    }
}

void solve(){
    //这里先一列列，然后一列列状态遍历，然后一行行决策
    for(int i=0;i<m;i++) for(int j=0;j<(1<<n);j++) if(dp[i][j]>0) dfs(0,i,j,0);
    cout<<dp[m][0]<<endl;
}

int main()
{
    while(cin>>n>>m&&n&&m) {init();solve();}
    return 0;
}

View Code

补充：其实这两个dp定义代码没什么太大区别。因为真正影响状态的只有横砖头操作。但是动态规划，要勇于尝试不同的定义，因为不同定义或许可以实现状态转移的优化，从而实现dp优化。