http://poj.org/problem?id=1038

发一下中文题面(今天考试直接被改了):

生记茶餐厅由于受杀人事件的影响,生意日渐冷清,不得不暂时歇业。四喜赋闲在家,整天抱着零食看电视,在大家的提醒下才开始注意自己日益发福的形象,下定决心减肥,萌发了去工作压力大的电脑公司打工的念头。于是,她应聘到了 Bugs 公司,这是一家专门生产硬件的企业。初来乍到,四喜被分配到车间进行产品组装,工作就是把公司生产的一种 2*3 单位尺寸的芯片嵌入 N*M 单位尺寸的模板内。模板接受过严格检查,损坏的单位小方格已被标上黑色记号,如下图所示。

【CEOI2002】【Poj 1038】Bugs Integrated, Inc.-LMLPHP

嵌入芯片的要求是,放置芯片的区域内不能有黑色记号,同时芯片与芯片之间不能重叠。公司为了追求利益,希望将尽量多的芯片嵌入模板,这可难坏了那批工人。四喜向你求助,希望你能帮她计算出可能嵌入的最大芯片数量。

①记忆化搜索

悲剧

【CEOI2002】【Poj 1038】Bugs Integrated, Inc.-LMLPHP

怎么改都MLE 。。。只能用map动态开内存,但是常数。。。

状态很小,3^10,记录每个点往下还要扩展几格(三格的直接忽略-直接转到下一层了)

// <bugs-b.cpp> - Thu Oct 20 08:13:16 2016
// This file is made by YJinpeng,created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is. #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#pragma GCC push_options
#pragma GCC optimize ("O2")
#define IN inline
#define RG register
using namespace std;
const int MAXN=;
inline int gi() {
register int w=,q=;register char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-')q=,ch=getchar();
while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();
return q?-w:w;
}
int n,m,g[MAXN][],mul[],a[];
map<int,int>f[MAXN];map<int,bool>u[MAXN];
IN int dfs(RG int d){
if(d==n+)return ;
int s=;
for(int i=;i<=m;i++)s+=mul[i]*a[i];
if(u[d][s])return f[d][s];u[d][s]=;
struct kai{
int d,c,b[];
IN void work(int x,int o){
for(int i=x;i<=m;i++)if(a[i])a[i]--;
c=max(c,dfs(d+)+o);//this
for(int i=x;i<=m;i++)a[i]=b[i];
if(x>m)return;
for(int i=x;i<m;i++){
if(d<n&&a[i]==&&a[i+]==&&!g[d][i]&&!g[d][i+]&&!g[d+][i]&&!g[d+][i+]){
if(d<=n-&&!g[d+][i]&&!g[d+][i+]){
a[i]=a[i+]=;//this
work(i+,o+);
a[i]=a[i+]=;
}
if(i<m-&&a[i+]==&&!g[d][i+]&&!g[d+][i+]){
a[i]=a[i+]=a[i+]=;//this
work(i+,o+);
a[i]=a[i+]=a[i+]=;
}
}
if(a[i])a[i]--;
}for(int i=x;i<=m;i++)a[i]=b[i];
}
void pre(int x){
c=;d=x;for(int i=;i<=m;i++)b[i]=a[i];
}
}e;e.pre(d);e.work(,);
return f[d][s]=e.c;
}
int main()
{
int T=gi();
while(T--){
for(int i=;i<MAXN;i++)
f[i].clear(),u[i].clear();
memset(g,,sizeof(g));
n=gi(),m=gi();int k=gi();
for(int i=;i<=k;i++)g[gi()][gi()]=;
mul[]=;for(int i=;i<=m;i++)mul[i]=mul[i-]*;
printf("%d\n",dfs());
}
return ;
}

吐槽:POJ居然卡空间,不得不用map(十倍常数)用数组0.03s就过了今天考试~~表示愤怒,我还是要把我的MLE的代码蒯上.(跑得比状压dp快)

// <bugs-s.cpp> - Thu Oct 20 08:13:16 2016
// This file is made by YJinpeng,created by XuYike's black technology automatically.
// Copyright (C) 2016 ChangJun High School, Inc.
// I don't know what this program is. #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#pragma GCC push_options
#pragma GCC optimize ("O2")
#define IN inline
#define RG register
using namespace std;
const int MAXN=;
const int MAXM=;
inline int gi() {
register int w=,q=;register char ch=getchar();
while((ch<''||ch>'')&&ch!='-')ch=getchar();
if(ch=='-')q=,ch=getchar();
while(ch>=''&&ch<='')w=w*+ch-'',ch=getchar();
return q?-w:w;
}
int n,m,g[MAXN][],mul[],a[];
int f[MAXN][MAXM];bool u[MAXN][MAXM];
IN int dfs(RG int d){
if(d==n+)return ;
int s=;
for(int i=;i<=m;i++)s+=mul[i]*a[i];
if(u[d][s])return f[d][s];u[d][s]=;
struct kai{
int d,c,b[];
IN void work(int x,int o){
for(int i=x;i<=m;i++)if(a[i])a[i]--;
c=max(c,dfs(d+)+o);//this
for(int i=x;i<=m;i++)a[i]=b[i];
if(x>m)return;
for(int i=x;i<m;i++){
if(d<n&&a[i]==&&a[i+]==&&!g[d][i]&&!g[d][i+]&&!g[d+][i]&&!g[d+][i+]){
if(d<=n-&&!g[d+][i]&&!g[d+][i+]){
a[i]=a[i+]=;//this
work(i+,o+);
a[i]=a[i+]=;
}
if(i<m-&&a[i+]==&&!g[d][i+]&&!g[d+][i+]){
a[i]=a[i+]=a[i+]=;//this
work(i+,o+);
a[i]=a[i+]=a[i+]=;
}
}
if(a[i])a[i]--;
}for(int i=x;i<=m;i++)a[i]=b[i];
}
void pre(int x){
c=;d=x;for(int i=;i<=m;i++)b[i]=a[i];
}
}e;e.pre(d);e.work(,);
return f[d][s]=e.c;
}
int main()
{
freopen("bugs.in","r",stdin);
freopen("bugs.out","w",stdout);
int T=gi();
while(T--){
memset(f,,sizeof(f));
memset(u,,sizeof(u));
memset(g,,sizeof(g));
n=gi(),m=gi();int k=gi();
for(int i=;i<=k;i++)g[gi()][gi()]=;
mul[]=;for(int i=;i<=m;i++)mul[i]=mul[i-]*;
printf("%d\n",dfs());
}
return ;
}

②状压DP

YZC今天给我讲了一下思路,第一行和第二行的状态一定是一样的,关键第三行,开两个数组分别记录第一行和第三行

挖坑待填~(有时间再写)

05-13 03:15
查看更多