大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168842.html原文链接：https://javaforall.net
