1、芯片（chip.pas/cpp）
【问题描述】
企鹅集成电路公司生产了一种大小为 2×3的芯片。每块芯片是从一块大小为N×M的硅
片上切下来的，但由于原材料纯度问题，因而有若干的单位正方形并不能作为芯片的一部分。
企鹅集成电路公司想要知道，给定一块 N×M大小的硅片和坏掉的单位正方形的位置，最
多能使用这块硅片生产多少芯片？
【输入格式】
输入的第一行由一个正整数 D 构成，表示硅片的个数。
随后跟着 D 个数据，每个数据第一行包含三个整数 N，M，K，分别表示硅片的长和宽，
以及硅片坏掉的单位正方形个数。
接下 K 行，每行两个整数 X ， Y ，表示单位正方形的坐标。
注：左上角的单位正方形用 (1,1) 表示，右下角的单位正方形用 (N,M) 表示。
【输出格式】
共 D 行，每行一个整数，即最多能切出多少个芯片。
【输入样例】
1
6 6 5
1 4
4 6
2 2
3 6
6 4
【输出样例】
3
【数据范围】
对于 10% 的数据，K=0；
对于另 外10%的数据，1≤M≤5，K≤1；
对于40%的数据，1≤M≤8；
最后一个测试点，空间限制8MB，其余限制64MB。
对于所有数据，1≤D≤5，1≤N≤150，1≤M≤10，0≤K≤M。
好。看一看就发现是状压DP，不会写，写了个搜索拿40分，稳的很。
#include <cstdio>
#include <cstring> const int N = ; bool vis[N][];
int ans, n, m; inline void read(int &x) {
x = ;
char c = getchar();
while(c > '' || c < '') {
c = getchar();
}
while(c >= '' && c <= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} inline int getmax(int x, int y) {
int tp = ;
for(int i = x; i <= n; i++) {
for(int j = (i == x) ? y : ; j <= m; j++) {
if(!vis[i][j]) {
tp++;
}
}
}
return tp / ;
} inline bool valid1(int x, int y) {
if(x + > n || y + > m) {
return ;
}
for(int i = x; i <= x + ; i++) {
for(int j = y; j <= y + ; j++) {
if(vis[i][j]) {
return ;
}
}
}
return ;
} inline bool valid2(int x, int y) {
if(x + > n || y + > m) {
return ;
}
for(int i = x; i <= x + ; i++) {
for(int j = y; j <= y + ; j++) {
if(vis[i][j]) {
return ;
}
}
}
return ;
} void DFS(int k, int x, int y) {
if(k > ans) {
ans = k;
}
if(y > m) {
y = ;
x++;
}
if(x > n) {
return;
}
int t = getmax(x, y);
if(k + t <= ans) {
return;
}
for(int i = x; i <= n; i++) {
for(int j = (i == x) ? y : ; j <= m; j++) {
if(valid1(i, j)) {
for(int a = i; a <= i + ; a++) {
vis[a][j] = ;
vis[a][j + ] = ;
}
DFS(k + , i, j + );
for(int a = i; a <= i + ; a++) {
vis[a][j] = ;
vis[a][j + ] = ;
}
}
if(valid2(i, j)) {
for(int b = j; b <= j + ; b++) {
vis[i][b] = ;
vis[i + ][b] = ;
}
DFS(k + , i, j + );
for(int b = j; b <= j + ; b++) {
vis[i][b] = ;
vis[i + ][b] = ;
}
}
}
}
return;
} int main() {
freopen("chip.in", "r", stdin);
freopen("chip_bf.out", "w", stdout);
int T;
read(T);
while(T--) {
int k;
ans = ;
memset(vis, , sizeof(vis));
read(n); read(m); read(k);
for(int i = , x, y; i <= k; i++) {
read(x); read(y);
vis[x][y] = ;
} DFS(, , ); printf("%d\n", ans);
} return ;
}
40分搜索
因为我用了一些奇淫技巧剪枝，是搜索中最稳的。
正解：轮廓线DP。
因为最高只有3，那么我们用三进制。
0 表示第 i 行与 i - 1 行皆为空。
1 表示第 i 行为空，i - 1 行被占用。
2 表示第 i 行被占用，i - 1任意。
转移的时候：枚举 i - 1 行的状态 j ，然后根据 j 推出什么都不放时的第 i 行的状态(即每一位 - 1)
考虑第 i 行每个位置放某个方格的左下角。
DFS转移：从第 i 行第一格开始转移。有三种选择：
放一个竖着的，DFS第三格
放一个横着的，DFS第四格
不放，DFS第二格
以此类推。
滚动数组优化：研究转移代码，发现只用到了 i - 1 行
开两个，用 i & 1
三进制状压：zip和unzip函数，指针的用法：
inline void unzip(int x, int *a) {
for(int i = m - ; i >= ; i--) {
a[i] = x % ;
x /= ;
}
return;
}
inline int zip(int *a) {
int x = ;
for(int i = ; i < m; i++) {
x = x * + a[i];
}
return x;
}
三进制状压
乱七八糟的知识点...
看代码看代码。
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = , M = ; int tri[M], f[N][], pre[M], now[M];
int m, n, G[N][M]; inline void unzip(int x, int *a) {
for(int i = m - ; i >= ; i--) {
a[i] = x % ;
x /= ;
}
return;
}
inline int zip(int *a) {
int x = ;
for(int i = ; i < m; i++) {
x = x * + a[i];
}
return x;
} void DFS(int x, int y, int last_ans, int now_sta) {
f[x][now_sta] = std::max(f[x][now_sta], last_ans); /// error : down
if(y + >= m) {
return;
} /// here
DFS(x, y + , last_ans, now_sta);
if(!now[y] && !now[y + ] && !pre[y] && !pre[y + ]) {
now[y] = now[y + ] = ;
int temp = zip(now);
DFS(x, y + , last_ans + , temp);
now[y] = now[y + ] = ;
}
if(y + < m && !now[y] && !now[y + ] && !now[y + ]) {
now[y] = now[y + ] = now[y + ] = ;
int temp = zip(now);
DFS(x, y + , last_ans + , temp);
now[y] = now[y + ] = now[y + ] = ;
}
return;
} int main() {
freopen("chip.in", "r", stdin);
freopen("chip.out", "w", stdout);
tri[] = ;
for(int i = ; i < ; i++) {
tri[i] = tri[i - ] * ;
}
int T;
scanf("%d", &T);
while(T--) {
int k;
scanf("%d%d%d", &n, &m, &k);
memset(f, -, sizeof(f));
memset(G, , sizeof(G));
int x, y;
while(k--) {
scanf("%d%d", &x, &y);
G[x][y - ] = ;
}
for(int i = ; i < m; i++) {
pre[i] = G[][i] + ; /// error : G[1][m]
}
int temp = zip(pre);
f[][temp] = ;
for(int i = ; i <= n; i++) { /// hang
for(int j = ; j < tri[m]; j++) { /// i - 1 : state j
if(f[i - ][j] == -) {
continue;
}
unzip(j, pre);
for(int k = ; k < m; k++) { /// get i state
if(G[i][k]) {
now[k] = ; /// error : now[i]
}
else {
now[k] = std::max(pre[k] - , );/// error : now[i] pre[i]
}
}
temp = zip(now);
DFS(i, , f[i - ][j], temp); /// DFS trans
}
}
int ans = ;
for(int i = ; i < tri[m]; i++) { /// get ans
ans = std::max(ans, f[n][i]);
}
printf("%d\n", ans);
} return ;
}
普通
#include <cstdio>
#include <algorithm>
#include <cstring> const int N = , M = ; int tri[M], f[][], pre[M], now[M];
int m, n, G[N][M]; inline void unzip(int x, int *a) {
for(int i = m - ; i >= ; i--) {
a[i] = x % ;
x /= ;
}
return;
}
inline int zip(int *a) {
int x = ;
for(int i = ; i < m; i++) {
x = x * + a[i];
}
return x;
} void DFS(int x, int y, int last_ans, int now_sta) {
f[x & ][now_sta] = std::max(f[x & ][now_sta], last_ans); /// error : down
if(y + >= m) {
return;
} /// here
DFS(x, y + , last_ans, now_sta);
if(!now[y] && !now[y + ] && !pre[y] && !pre[y + ]) {
now[y] = now[y + ] = ;
int temp = zip(now);
DFS(x, y + , last_ans + , temp);
now[y] = now[y + ] = ;
}
if(y + < m && !now[y] && !now[y + ] && !now[y + ]) {
now[y] = now[y + ] = now[y + ] = ;
int temp = zip(now);
DFS(x, y + , last_ans + , temp);
now[y] = now[y + ] = now[y + ] = ;
}
return;
} int main() {
freopen("chip.in", "r", stdin);
freopen("chip_bf.out", "w", stdout);
tri[] = ;
for(int i = ; i < ; i++) {
tri[i] = tri[i - ] * ;
}
int T;
scanf("%d", &T);
while(T--) {
int k;
scanf("%d%d%d", &n, &m, &k);
memset(G, , sizeof(G));
memset(f, -, sizeof(f));
int x, y;
while(k--) {
scanf("%d%d", &x, &y);
G[x][y - ] = ;
}
for(int i = ; i < m; i++) {
pre[i] = G[][i] + ; /// error : G[1][m]
}
int temp = zip(pre);
f[][temp] = ;
for(int i = ; i <= n; i++) { /// hang
for(int j = ; j < tri[m]; j++) {
f[i & ][j] = -;
}
for(int j = ; j < tri[m]; j++) { /// i - 1 : state j
if(f[(i + ) & ][j] == -) {
continue;
}
unzip(j, pre);
for(int k = ; k < m; k++) { /// get i state
if(G[i][k]) {
now[k] = ; /// error : now[i]
}
else {
now[k] = std::max(pre[k] - , );/// error : now[i] pre[i]
}
}
temp = zip(now);
DFS(i, , f[(i + ) & ][j], temp); /// DFS trans
}
}
int ans = ;
for(int i = ; i < tri[m]; i++) { /// get ans
ans = std::max(ans, f[n & ][i]);
}
printf("%d\n", ans);
} return ;
}
滚动数组优化空间
这几个错调的真不容易啊......
#include<bits/stdc++.h>
using namespace std; const int tri[] = {, , , , , , , , , , , };
int n, m, k, dp[][], pre[], now[]; //滚动数组来记录
bool g[][];
int getTen(int *a)//把一个用数组表示的状态转化为一个10进制整数
{
int ans = ;
for(int i = ; i <= m; ++i)
ans += a[i]*tri[i];
return ans;
}
void getTri(int v, int *a)//把一个整数转化为一个数组来表示状态
{
for(int i = ; i <= m; ++i) {
a[i] = v%;
v /= ;
}
}
void dfs(int x, int y, int last, int key)
{
int k;
dp[x&][key] = max(dp[x&][key], last);
if(y >= m) return;
if(!pre[y] && !pre[y+] && !now[y] && !now[y+]) {//竖着切割
now[y] = now[y+] = ;
k = getTen(now);
dfs(x, y+, last+, k);
now[y] = now[y+] = ;
}
if(y<m- && !now[y] && !now[y+] && !now[y+]) { //横着切割 now[y] = now[y+] = now[y+] = ;
k = getTen(now);
dfs(x, y+, last+, k);
now[y] = now[y+] = now[y+] = ;
}
dfs(x, y+, last, key); //不做改动，直接下一行
}
int main()
{
freopen("chip.in","r",stdin);
freopen("chip.out","w",stdout);
int t, a, b, tmp;
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n, &m, &k);
memset(g, , sizeof(g));
for(int i = ; i < tri[m+]; ++i) dp[][i] = -;
for(int i = ; i < k; ++i) {
scanf("%d%d", &a, &b);
g[a][b] = ;
}
for(int i = ; i <= m; ++i)
pre[i] = g[][i]+; //设置第一行的状态，第0行的方块全部视为不可用
tmp = getTen(pre);
dp[][tmp] = ;
for(int i = ; i <= n; ++i) {
for(int j = ; j < tri[m+]; ++j) dp[i&][j] = -;
for(int j = ; j < tri[m+]; ++j) {
if(dp[(i+)&][j] == -) continue; //跳过不可能的子状态
getTri(j, pre);
for(int l = ; l <= m; ++l) //根据上一行的状态得到本行的状态
if(g[i][l]) now[l] = ;
else now[l] = max(pre[l]-, );
tmp = getTen(now);
dfs(i, , dp[(i+)&][j], tmp);
}
}
int ans = ;
for(int i = ; i < tri[m+]; ++i)
ans = max(ans, dp[n&][i]);
printf("%d\n", ans);
}
return ;
}
std