面试题(状态压缩dp)

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

题解
状态压缩dp,f[i][j]代表第i行状态为j的方案数

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define send string::npos
#define lowbit(x) (x&(-x))
#define left(x) x<<1
#define right(x) x<<1|1
#define transformu(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define transformd(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
typedef long long ll;
typedef pair<long long,long long> PII;
typedef pair<double,double>PDD;
typedef struct Node * pnode;
const long long N = 1e3  + 10;
const long long M = 4 * N;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const long long Mod = 4e8;
const long long INF = 0x3f3f3f3f;
const double eps = 1e-6;
PII g[N * N ];
int a[N];
int cnt = 0;
int f[2][N * N];
int z[N];
int n;
bool check(int x){ 

int a = g[x].x,b = g[x].y;
for(int i = a;i <= a + b - 1;i ++){ 

if(z[i] == 0)return false;
}
return true;
}
int main(){ 

cnt ++;
// cout<<cnt<<endl;
cin>>n;
for(int len = 1;len <= n;len ++){ 

for(int i = 0;i <= n - len;i ++){ 

g[cnt].x = i,g[cnt].y = len;
cnt ++;
}
}
// cout<<cnt<<endl;
char x;
f[0 & 1][0] = 0;
for(int i = 1;i <= n + 1;i ++){ 

memset(z,0,sizeof z);
for(int j = 0;j < n && i != n + 1;j ++){ 

cin>>x;
if(x == '.')z[j] = 1;
}
// for(int j = 0;j < n;j ++)cout<<z[j]<<endl;
for(int j = 0;j < cnt;j ++){ 

if(check(j) && j != 0){ 

f[i & 1][j]  = f[(i - 1) & 1][j] + 1;
}
else if(j != 0){ 

f[i & 1][j] = 0;
}
else if(j == 0){ 

for(int k = 0;k < cnt;k ++)
f[i & 1][j] += f[(i - 1) & 1][k];
cout<<f[i & 1][j]<<endl;
}
}
}
// cout<<n + 1<<endl;
cout<<f[(n + 1) & 1][0]<<endl;
return 0;
}