欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 1400 插头DP,状压DP

程序员文章站 2022-06-09 19:02:05
...

HDU 1400

状态压缩DP

逐行进行。详细看注释。跑出4s。Q_Q

#include<bits/stdc++.h>
#define debug(_x) cout<<#_x<<":"<<_x<<endl
#define endl '\n'
using namespace std;
using ll = long long;
ll f[2][1<<12],*f1,*f0;
int n,m;
bool judge(int s,int t){
    short cnt=0;
    for(int i=0;i<m;++i){
        if(!(t&1) && !(s&1))return false;  // 上一行为空的位置,下一行必须竖着放,即两行不能同为0
        if(t&1 && s&1){  // 如果两行同时为1,则必为横放
            cnt++;
        }
        else{
            if(cnt&1)return false;  // 横放必为偶数个连续
            cnt=0;
        }
        t>>=1;
        s>>=1;
    }
    return !(cnt&1);
}
int main(){
    int T;
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    while(cin>>n>>m && n){
        f0=f[0];f1=f[1];
        fill(f0,f0+(1<<m),0);
        f0[(1<<m)-1]=1;   // 上一行全为满的,即不能放上去
        for(int i=0;i<n;++i){
            fill(f1,f1+(1<<m),0);
            for(int j=0;j<1<<m;++j){
                for(int k=0;k<1<<m;++k){
                    if(judge(j,k))f1[j]+=f0[k];
                }
            }
            swap(f0,f1);
        }
        cout<<f0[(1<<m)-1]<<endl;
    }
}

轮廓线DP

逐格进行,竖放和不放其实可以写在一起f1[s^(1<<j)]+=f0[s]。下面图中,红线为轮廓线,即已决策状态和未决策状态的交界线。dp的状态就是轮廓线上的方格是否已放。跑出15ms。^ _ ^
当上一行为0时,必须竖放。
HDU 1400 插头DP,状压DP
当上一行为1时,可以不放。
HDU 1400 插头DP,状压DP
当上一行为0且左边为0时,可以横放。
HDU 1400 插头DP,状压DP

#include<bits/stdc++.h>
#define debug(_x) cout<<#_x<<":"<<_x<<endl
#define endl '\n'
using namespace std;
using ll = long long;
ll f[2][1<<12],*f1,*f0;
int n,m;
int main(){
    int T;
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    while(cin>>n>>m && n){
        f0=f[0];f1=f[1];
        fill(f0,f0+(1<<m),0);
        f0[(1<<m)-1]=1;
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                fill(f1,f1+(1<<m),0);
                for(int s=0;s<1<<m;++s){
                    if(!((s>>j)&1)){  // 上一行j位置为空,需要竖着放
                        f1[s^(1<<j)]+=f0[s];
                    }else{
                        if(j && !(s&(1<<j-1)))  // j-1位置为空,可以横着放
                            f1[s^1<<j-1]+=f0[s];
                        f1[s^(1<<j)]+=f0[s];  // 不放
                    }
                }
                swap(f0,f1);
            }
        }
        cout<<f0[(1<<m)-1]<<endl;
    }
}
相关标签: ACM训练 acm竞赛