經典的狀態(tài)壓縮DP，《算法藝術與信息學競賽》的例題。f[i][j]表示前i行，最后兩行狀態(tài)為二進制數(shù)j，嵌入的最多芯片數(shù)。第i行到第i+1行用DFS進行狀態(tài)轉移。
由于第i+1行只和第i行有關，故可以用滾動數(shù)組優(yōu)化。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2000-9-12 11:08:54
File Name: pku1038.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 150;
const int maxm = 10;
int n, m, k;
int g[maxn];
int cnt_mask;
int mask[30];
int f[2][1 << (2 * maxm)];
void generate_mask()
{
cnt_mask = 0;
for (int i = 0; i < m - 2; i++)
{
int tmp = 0;
tmp |= 7 << (2 * m + i);
tmp |= 7 << (m + i);
mask[cnt_mask++] = tmp;
tmp = 0;
tmp |= 7 << (m + i);
tmp |= 7 << (i);
mask[cnt_mask++] = tmp;
}
for (int i = 0; i < m - 1; i++)
{
int tmp = 0;
tmp |= 3 << (2 * m + i);
tmp |= 3 << (m + i);
tmp |= 3 << (i);
mask[cnt_mask++] = tmp;
}
}
void dfs(int row, int org_t, int now_t, int now, int cnt)
{
f[(row + 1) % 2][now_t & ((1 << (2 * m)) - 1)] >?= f[row % 2][org_t] + cnt;
for (int i = now; i < cnt_mask; i++)
if ((now_t & mask[i]) == 0)
dfs(row, org_t, now_t | mask[i], i + 1, cnt + 1);
}
int dp()
{
memset(f, -1, sizeof(f));
f[1][(g[0] << m) | g[1]] = 0;
int end = (1 << (2 * m));
for (int i = 1; i < n - 1; i++)
{
for (int j = 0; j < end; j++) if (f[i % 2][j] != -1)
{
int t = (j << m) | g[i + 1];
dfs(i, j, t, 0, 0);
}
memset(f[i % 2], -1, sizeof(f[i % 2]));
}
int ret = 0;
for (int i = 0; i < end; i++)
ret >?= f[(n - 1) % 2][i];
return ret;
}
int main()
{
int ca;
for (scanf("%d", &ca); ca--;)
{
scanf("%d%d%d", &n, &m ,&k);
memset(g, 0, sizeof(g));
for (int i = 0; i < k; i++)
{
int x, y;
scanf("%d%d", &x, &y);
g[x - 1] |= 1 << (y - 1);
}
generate_mask();
printf("%d\n", dp());
}
return 0;
}