题目链接
题目思路
设\(dp[i][j]\)表示前\(i-1\)列全部合法\(j\)表示第\(i,i+1,i+2,i+3\)列的状态
转移的话只要枚举这一列进行了什么操作即可
复杂度\(O(n*2^{16}*(4+3+2+1))\)
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e3+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n;
int a[10];
char s[5][maxn];
int sta[maxn];
int dp[maxn][(1<<16)+1];
int c[10][10];
vector<int> f[10];
signed main(){
scanf("%d",&n);
for(int i=1;i<=4;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=4;i++){
scanf("%s",s[i]+1);
}
for(int i=1;i<=4;i++){//
for(int j=1;j<=1;j++){// 只要考虑一列就行 不要枚举到4
for(int k=1;k<=4-max(i,j)+1;k++){//左上角[i,j]里面放长度为k的正方形
for(int a=1;a<=4;a++){
for(int b=1;b<=4;b++){
c[a][b]=1;
}
}
for(int a=i;a<=i+k-1;a++){
for(int b=j;b<=j+k-1;b++){
c[a][b]=0;
}
}
int now=0;
for(int b=4;b>=1;b--){
for(int a=4;a>=1;a--){
now=now*2+c[a][b];
}
}
f[k].push_back(now);
}
}
}
for(int i=4;i>=1;i--){
for(int j=1;j<=n;j++){
sta[j]=sta[j]*2;
if(s[i][j]==‘*‘) sta[j]++;
}
}
int now=0;
for(int j=1;j<=4;j++){
now+=(sta[j]<<(4*(j-1)));
}
memset(dp,0x3f,sizeof(dp));
dp[1][now]=0;
for(int i=1;i<=n;i++){
for(int j=(1<<16)-1;j>=0;j--){
if(dp[i][j]==inf) continue;
if(!(j&15)){
int now=((j>>4)|sta[i+4]<<12);
dp[i+1][now]=min(dp[i+1][now],dp[i][j]);
}
for(int k=1;k<=4;k++){
for(auto x:f[k]){
dp[i][j&x]=min(dp[i][j&x],dp[i][j]+a[k]);
}
}
}
}
printf("%d\n",dp[n][0]);
return 0;
}