Clear The Matrix CodeForces - 903F (状压)

大意: 给定4行的棋盘以及4种大小的正方形方块, 每种各有一定花费, 每次可以选一种方块放在棋盘上, 棋盘对应格子全变为'.', 求最少花费使得棋盘全部变成'.'

状压基本操作练习, 状态取12位, 暴力DP, 这里用0表示'.', 1表示'*', 用较小的列做低位, 前推状态, 具体见代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define pb push_back
using namespace std; const int N = 1e3+10, M = (1<<12)-1, INF = 0x3f3f3f3f;
int n, c[4];
char s[4][N];
int sta[N], dp[N][M+10];
vector<int> mat[3];
void chkmin(int &x,int y) {x=min(x,y);} int main() {
scanf("%d", &n);
REP(i,0,3) scanf("%d", c+i);
REP(i,0,3) scanf("%s", s[i]);
REP(i,0,2) REP(j,0,3) {
int t = M;
REP(k,j,min(3,i+j)) {
REP(kk,0,i) t ^= 1<<(k+4*kk);
}
mat[i].pb(t);
}
REP(i,0,3) REP(j,0,n-1) (sta[j]<<=1)|=(s[i][j]=='*');
memset(dp, 0x3f, sizeof dp);
dp[0][sta[0]^(sta[1]<<4)^(sta[2]<<8)] = 0;
REP(i,0,n-1) PER(j,0,M) if (dp[i][j]!=INF) {
if (!(j&15)) chkmin(dp[i+1][(j>>4)^(sta[i+3]<<8)],dp[i][j]);
chkmin(dp[i+1][0], dp[i][j]+c[3]);
REP(k,0,2) for (int kk:mat[k]) {
chkmin(dp[i][j&kk], dp[i][j]+c[k]);
}
}
printf("%d\n", dp[n-1][0]);
}
上一篇:Codeforces 903F Clear The Matrix(状态压缩DP)


下一篇:STM32F0xx_TIM输出PWM配置详细过程