HDU 1400 插头DP,状压DP
程序员文章站
2022-06-09 19:02:05
...
状态压缩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时,必须竖放。
当上一行为1时,可以不放。
当上一行为0且左边为0时,可以横放。
#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;
}
}
上一篇: 根据AD账号直接单点登录到第三方系统