题目
题解
题意：给定一个4×n的长方形网格，其中一些是’ ∗ * ∗’，一些是’ . . .’。可以进行若干次清理操作，每次选择一个大小为 k × k ( 1 ⩽ k ⩽ 4 ) k×k(1⩽k⩽4) k×k(1⩽k⩽4)的正方形网格，将其中的‘ ∗ * ∗’变为‘ . . .’，花费 a k a_k ak​。问，将所有网格都变为‘ . . .’的最小花费。

Solution

由于选择4×4的网格进行清理的时候，相当于强行转移阶段，剩下的就是1⩽k⩽3的情况，我们只需要压最后的3列4行就好了
更新有点类似01背包

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1002;
int i,j,d,x,y,s,a[4],tmp,f[N][1<<12],n,st[N];
char s1[4][N];
vector<int>v[4];
inline void M(int &x,int y){if(y<x)x=y;}
int main(){
	scanf("%d",&n);
	for (i=0;i<4;i++) scanf("%d",&a[i]);
	for (i=0;i<4;i++) scanf("%s",s1[i]);
	for (i=0;i<n;i++)
		for (j=0;j<4;j++) st[i]=st[i]<<1|(s1[j][i]=='*');
	for (i=0;i<3;i++)
		for (j=0;j<4;j++)
			for (d=0;i+d<3 && j+d<4;d++){
				tmp=(1<<12)-1;
				for (x=i;x<=i+d;x++)
					for (y=j;y<=j+d;y++) tmp^=1<<x*4+y;
				v[d].push_back(tmp);
			}
	memset(f,63,sizeof(f));
	f[2][st[2]|st[1]<<4|st[0]<<8]=0;
	for (i=2;i<n;i++)
		for (s=(1<<12)-1;~s;s--)
			if (f[i][s]<1e9){
				if (s<(1<<8)) M(f[i+1][s<<4|st[i+1]],f[i][s]);
				M(f[i+1][0],f[i][s]+a[3]);
				for (d=0;d<3;d++)
					for (j=0;j<v[d].size();j++) M(f[i][s&v[d][j]],f[i][s]+a[d]);
			}
	printf("%d",f[n-1][0]);
}