[POJ1038]状压DP

题意：给一个n*m的区域，里面有一些障碍物，往里面放2*3和3*2的矩形，矩形之间不能重叠，不能覆盖到障碍物，求能放置的最大个数。(n<=150,m<=10)

思路：看到m=10就应该往状压dp方面想了。由于有3*2的矩形，所以需要记录2行的状态，粗略估计状态数高达150*2^20=1.5*1e8，这么多状态必然超时，注意到如果(i-1,j)为0了，无论(i,j)为1或0，(i,j)都不能放矩形，于是知道有很多无用的或者说不合法的状态，两行的状态用m位3进制数表示同样能实现转移。由于3进制数操作起来麻烦，不妨用4进制代替3进制，从当前状态向后递推，新状态存在vector里，使用的时候先排序，然后跳过重复或不够优的状态来向后扩展。经测试，极限数据下，vector里有40000多个状态，有效状态只有1700多个，一下子降了一个数量级，简直逆天...对于这种存在大量无效状态的dp ，用vector+向后递推+排序去重有奇效。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cstring>

#include <vector>

#include <ctime>

#include <deque>

#include <queue>

#include <algorithm>

using namespace std;

void readInt(){}void RI(int&X){scanf("%d",&X);}template<typename...R>

void RI(int&f,R&...r){RI(f);RI(r...);}void RIA(int*p,int*q){int d=p<q?1:-1;

while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>

void print(const T t){cout<<t<<endl;}template<typename F,typename...R>

void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>

void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}

template<typename T>bool umax(T &a, const T &b) {

return a >= b? false : (a = b, true);

}

typedef pair<int, int> pii;

#define pb push_back

#define mp make_pair

#define X first

#define Y second

#define all(a) (a).begin(), (a).end()

vector<pii> dp[2];

bool cmp(const pii &a, const pii &b) {

return a.X < b.X || a.X == b.X && a.Y > b.Y;

}

int sta[157], now, row, ttl, n, m, k;

pii s;

bool chk(const int &s, const int &p) {

return s & (1 << p);

}

void dfs(int col, int S, int V) {

if (col == m) {

dp[now ^ 1].pb(mp(S, V));

return ;

}

dfs(col + 1, S, V);

int low = S & ttl, high = S >> m, r = low | high;

if (col + 2 < m && !chk(r, col) && !chk(r, col + 1) && !chk(r, col + 2)) {

int h = (1 << col) ^ (1 << (col + 1)) ^ (1 << (col + 2));

dfs(col + 3, (high ^ h) << m | (low ^ h), V + 1);

}

r |= s.X >> m;

if (col + 1 < m && !chk(r, col) && !chk(r, col + 1)) {

int h = (1 << col) ^ (1 << (col + 1));

dfs(col + 2, (high ^ h) << m | (low ^ h), V + 1);

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif // ONLINE_JUDGE

int T;

cin >> T;

while (T --) {

RI(n, m, k);

memset(sta, 0, sizeof(sta));

for (int i = 0; i < k; i ++) {

int x, y;

RI(x, y);

sta[x] ^= 1 << (y - 1);

}

dp[0].clear();

dp[1].clear();

now = 0;

ttl = (1 << m) - 1;

dp[0].pb(mp(ttl << m | sta[1], 0));

for (int i = 1; i < n; i ++) {

dp[now ^ 1].clear();

sort(all(dp[now]), cmp);

int sz = dp[now].size();

for (int j = 0; j < sz; j ++) {

s = dp[now][j];

if (!j || s.X != dp[now][j - 1].X)

dfs(0, (s.X << m | sta[i + 1]) & (ttl << m | ttl), s.Y);

}

now ^= 1;

}

int ans = 0;

for (int i = 0; i < dp[now].size(); i ++) {

umax(ans, dp[now][i].Y);

}

cout << ans << endl;

}

return 0;

}

巴特西

[POJ1038]状压DP

最新文章

热门文章