标签：20 Covering int 600005 state Tile DP
- 从顶层设计的角度考虑，我们并不关心具体的放置骨牌的方法，而只关心这种覆盖是否可行
- 而一种覆盖可行等价于该覆盖中不存在“L型”
- 于是我们就可以优化轮廓线DP的设计以省去DP中构造方案所需要的时空复杂度
- 本题似乎还卡STL，下次涉及到大量入队出队操作的时候还是手写队列吧，毕竟也就一分钟左右的事
- 关于程序的错误一般会出现在何处，我想你已经有了一些经验
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int v[20][20],n,m;
int f[2][600005],maxn;
bool b[600005];
int q[2][600005],cnt[2];
bool opt;
void insert(int cur,int state,int w)
{
if(opt==true)
{
state=state&(~(1<<m));
state=(state<<1);
}
if(b[state]==false)
{
b[state]=true;
q[cur][++cnt[cur]]=state;
f[cur][state]=w;
}
f[cur][state]=max(f[cur][state],w);
maxn=max(maxn,f[cur][state]);
}
int get(int state,int k)
{
if(k==-1||k==m+1)
{
return 0;
}
return ((state>>k)&1);
}
int val(int k,int x)
{
return x*(1<<k);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>v[i][j];
}
}
int cur=0;
insert(0,0,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
opt=(j==m);
maxn=0;
memset(b,false,sizeof(b));
int tmp=0;
for(int k=1;k<=cnt[cur];k++)
{
int state=q[cur][k];
tmp=max(tmp,state);
int x=get(state,j-2),y=get(state,j-1),z=get(state,j),g=get(state,j+1),w=f[cur][state];
if(v[i][j]<=0)
{
insert(cur^1,state-val(j-1,y),w);
}
else
{
insert(cur^1,state-val(j-1,y),w);
if(!(x==1&&y==1)&&!(y==1&&z==1)&&!(z==1&&g==1)&&!(x==1&&z==1))
{
insert(cur^1,state-val(j-1,y)+val(j-1,1),w+v[i][j]);
}
}
}
cnt[cur]=0;
cur=cur^1;
}
}
cout<<maxn<<endl;
return 0;
}
标签：20,
Covering,
int,
600005,
state,
Tile,
DP
From： https://www.cnblogs.com/watersail/p/18308099