面试题(状态压缩dp)

全栈程序员-用户IM • 2022年8月9日上午11:00 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}