HDU 1438 钥匙计数之一（状压DP）题解

思路：

每个槽有4种深度，一共有2^4种状态。然后开4维来保存每一次的状态：dp[ 第几个槽 ][ 当前状态 ][ 末尾深度 ][ 是否符合要求 ]。

代码：

#include<cstdio>

#include<map>

#include<set>

#include<queue>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

const int N = 500+5;

const int INF = 0x3f3f3f3f;

using namespace std;

ll dp[32][1<<4+5][4][2];  //第几个槽，槽的状态，最后一个槽的深度，是否已经符合要求

int num[20];

int main(){

    memset(dp,0,sizeof(dp));

    memset(num,0,sizeof(num));

    for(int i = 0;i < 16;i++){

        for(int j = 0;j < 4;j++){

            if(i & (1<<j)) num[i]++;  //计算满足深度大于等于3

        }

    }

    dp[1][1][0][0] = dp[1][2][1][0] = dp[1][4][2][0] = dp[1][8][3][0] = 1;

    for(int i = 2;i <= 31;i++){ //第几个槽

        for(int j = 0;j < 16;j++){  //上一个槽状态

            for(int k = 0;k < 4;k++){  //上一个槽末尾

                for(int l = 0;l < 4;l++){  //这个槽末尾

                    int sta = j | (1<<l); //当前状态

                    dp[i][sta][l][1] += dp[i - 1][j][k][1];

                    if(k - l == 3 || l - k == 3){

                        dp[i][sta][l][1] += dp[i - 1][j][k][0];

                    }

                    else{

                        dp[i][sta][l][0] += dp[i - 1][j][k][0];

                    }

                }

            }

        }

    }

    ll ans;

    for(int i = 2;i <= 31;i++){

        ans = 0;

        for(int j = 0;j < 16;j++){

            if(num[j] >= 3){

                for(int k = 0;k < 4;k++){

                    ans += dp[i][j][k][1];

                }

            }

        }

        printf("N=%d: %lld\n",i,ans);

    }

    return 0;

}

巴特西

HDU 1438 钥匙计数之一（状压DP）题解

最新文章

热门文章