SGU 132 Another Chocolate Maniac
2020-03-06 16:00:37来源:博客园 阅读 ()
SGU 132 Another Chocolate Maniac
三进制状压DP,通过预先筛掉不合法状态优化,毒瘤卡常CodeForces题目页面传送门
给定一个\(n\times m\)的字符矩阵,每个字符是\(\texttt.\)或\(\texttt*\),分别表示空格和障碍物。在这个字符矩阵上放若干个\(1\times2\)或\(2\times1\)的骨牌,求最少放多少个使得没有空地再放。
\(n\in[1,70],m\in[1,7]\)。
看到\(m\)如此之小,很容易想到对最终状态的每行进行装压,然后再以行数作为阶段DP。
考虑最终状态有多少种格子,给每种分配一个编号状压。显而易见的有空格、障碍物和骨牌中的一格。因为如果一个格子在给定字符矩阵的时候是障碍物,那么它在最终形态中就必须是障碍物,相反,如果给定的时候不是障碍物,那么它在最终状态中也不可能是障碍物,所以不需要专门给障碍物设一个编号,让它随便和另一种状态用同一个编号即可,放到具体某行某列中自能识别是否障碍物。对于骨牌中的一格,由于它是\(1\times2\)还是\(2\times1\)的骨牌中的一格在向相邻行转移时情况是不一样的,所以要分出\(3\)种:\(1\times2\)骨牌中的一格、\(2\times1\)骨牌中的上格、\(2\times1\)骨牌中的下格。而在转移时,\(2\times1\)骨牌中的上下格是必须匹配的,所以又可以省去一个编号。于是编号就确定了:\(0\):空格,\(1\):\(1\times2\)骨牌中的一格或\(2\times1\)骨牌中的上格,\(2\):\(2\times1\)骨牌中的下格。至于障碍物到底跟谁共享编号,到下面再讨论。
接下来可以DP了。由于有\(3\)个编号,所以这是一个三进制状压DP。设\(dp_{i,j}\)表示第\(i\)行的格子的编号序列进行三进制状压后为\(j\),前\(i\)行满足题意时,最少的放骨牌的格子数量。设\(cnt(i,j)\)表示第\(i\)行状态为\(j\)时的放骨牌的格子数量,\(vld(i,j)\)表示第\(i\)行状态为\(j\)是否合法,\(cantrs(i,j,k)\)表示第\(i\)行状态为\(j\)、第\(i-1\)行状态为\(k\)是否合法,那么边界为\(dp_{1,i}=\begin{cases}cnt(1,i)&vld(1,i)\\\infty&\lnot vld(1,i)\end{cases}\),状态转移方程为\(dp_{i,j}=\begin{cases}\min\limits_{cantrs(i,j,k)}\{dp_{i-1,k}+cnt(i,j)\}&vld(i,j)\\\infty&\lnot vld(i,j)\end{cases}\),目标为\(\dfrac{\min\limits_{vld(n,i)}\{dp_{n,i}\}}2\)。
然而这样状态数是\(\mathrm O(3^mn)\),对于每个状态都有\(\mathrm O(3^m)\)个状态可转移,每次\(cantrs\)判断还要\(\mathrm O(m)\),于是总时间复杂度是\(\mathrm O(9^mnm)\),很明显过不去,于是考虑优化。不难发现题目中的限制“不能有空地再放”等价于在最终状态中不存在\(2\)个横/纵相邻的空格。
注意到\(vld\)的判断方法:\(vld_{i,j}\)当且仅当满足以下全部条件:
- \(j\)中没有相邻的空格;
- 第\(i\)行所有障碍物的格子在\(j\)中全是障碍物的编号;
- 如果\(i=1\),那么\(j\)中没有\(1\times2\)骨牌中的下格;
- 如果\(i=n\),那么\(j\)中所有\(1\times2\)骨牌中的一格组成的连续段长度都要是偶数。(这一条本来是要放到\(cantrs\)里判的,因为要根据下面一排哪些地方是\(2\times1\)骨牌中的下格才能知道本排所有编号为\(1\)的格子分别是是\(2\times1\)骨牌中的上格还是\(1\times2\)骨牌中的一格,才好做判断。但是第\(n\)排并没有下面一排,所以可以确定不存在\(2\times1\)骨牌中的上格,又在\(cantrs\)里判不到,只能拿到\(vld\)里来判)
其中第\(3,4\)条仅当\(i=1,n\)时才判,不管。第\(1\)条与DP的阶段\(i\)无关,于是我们可以将所有满足条件\(1\)的状态预先筛出来(如果障碍物与空格共享编号的话,会导致将可能在具体某一行中合法的状态判成不合法,于是障碍物的编号不能是\(0\),现在只剩下\(2\)个人选了——\(1,2\)),在DP过程中再判断第\(2\)条,避免多余判断。经计算,当\(m=7\)时会筛出来\(1224\)个状态,将近从\(3^m=2187\)个原有的状态中筛掉一半,看来效果不错,不过依然当\(n=70,m=7\)时最多要做约\(1224^2nm\approx 7\times10^8\)次运算,过不去。于是继续优化。
再来考虑\(cantrs\)的判断方法:\(cantrs_{i,j,k}\)当且仅当满足以下全部条件:
- \(j,k\)中没有纵相邻的空格;
- 对于所有\(j\)中是\(2\times1\)骨牌中的下格的位置,\(k\)中此位置是\(2\times1\)骨牌中的上格;
- \(k\)中所有\(1\times2\)骨牌中的一格组成的连续段长度都要是偶数。(因为要根据下面一排哪些地方是\(2\times1\)骨牌中的下格才能知道本排所有编号为\(1\)的格子分别是是\(2\times1\)骨牌中的上格还是\(1\times2\)骨牌中的一格,才好做判断,所以拿到\(cantrs\)里判)
其中第\(1,2\)条与DP的阶段\(i\)无关,而第\(3\)条看似无关,但其实有问题,先不管它。模仿\(vld\)的方法,\(\forall j\),其中\(j\)在\(vld\)筛出来的状态表中(否则DP值一定为\(\infty\),不用考虑转移),将所有满足条件\(2,3\)且在\(vld\)筛出来的状态表中(否则DP值一定为\(\infty\),不可能成为有效转移对象)的转移对象预先筛出来,此时我们会发现,如果障碍物的编号取\(2\)的话,又双叒叕会导致将可能在具体某一行中合法的转移判成不合法(第\(2\)条),于是障碍物的编号也不能是\(2\),所以就定下来了:\(1\)。此时,第\(2\)条又不能在预先筛的时候完全判断完毕了,DP过程中还要进一步判断。好了,我们现在来看第\(3\)条,由于现在障碍物的编号是\(1\)了,那么在\(i\)未知的情况下就无法判断编号是\(1\)的格子是否\(1\times2\)的骨牌,也就是说第\(3\)条与\(i\)有关了,于是不能列入预先筛的条件。如此又筛过一波后,经计算,当\(m=7\)时会筛出来\(129318\)个转移对,从\(1224^2=1498176\)个原有的转移对中筛掉了\(\dfrac1{10}\)还多!!现在当\(n=70,m=7\)时最多要做约\(129318nm\approx6\times10^7\)次运算,理论上能过去了。
于是开始写代码了:
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=70,M=7;
int n/*字符矩阵行数*/,m/*字符矩阵列数*/;
char a[N+1][M+5];//字符矩阵
vector<int> vld;//vld筛出来的状态表
vector<vector<int> > dgt;//每个三进制数的每一位
vector<vector<int> > trs;//cantrs筛出来的转移表
vector<int> dp[N+1];//DP数组
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int pow3=1;
for(int i=1;i<=m;i++)pow3*=3;
for(int i=0;i<pow3;i++){//预处理dgt&第1波筛
int dgt0[m],cpy=i;
for(int j=0;j<m;j++)dgt0[j]=cpy%3,cpy/=3;
bool ok=true;
for(int j=0;j+1<m;j++)ok&=dgt0[j]||dgt0[j+1];//vld条件1
if(ok)vld.pb(i),dgt.pb(vector<int>(dgt0,dgt0+m));
}
trs.resize(vld.size());
for(int i=0;i<vld.size();i++)for(int j=0;j<vld.size();j++){//第2波筛
bool ok=true;
for(int k=0;k<m;k++)ok&=(dgt[i][k]||dgt[j][k])/*cantrs条件1*/&&(dgt[i][k]!=2||dgt[j][k]==1)/*cantrs条件2*/;
if(ok)trs[i].pb(j);
}
for(int i=0;i<=n;i++)dp[i].resize(vld.size(),inf);
for(int i=0;i<vld.size();i++){//边界
bool ok=true;
int cnt=0;//放骨牌的格子的数量
for(int j=0;j<m;j++)ok&=dgt[i][j]!=2/*vld条件3*/&&(dgt[i][j]==1||a[1][j]=='.')/*vld条件2*/,cnt+=dgt[i][j]==1&&a[1][j]=='.';
if(ok)dp[1][i]=cnt;
}
for(int i=2;i<=n;i++)for(int j=0;j<vld.size();j++){//开始DP
bool ok=true;
int cnt=0;//放骨牌的格子的数量
for(int k=0;k<m;k++)ok&=dgt[j][k]==1||a[i][k]=='.'/*vld条件2*/,cnt+=dgt[j][k]==1&&a[i][k]=='.'||dgt[j][k]==2;
if(!ok)continue;
for(int k=0;k<trs[j].size();k++){
int trs0=trs[j][k];
ok=true;
for(int o=0;o<m;o++)ok&=dgt[j][o]!=2||dgt[trs0][o]==1&&a[i-1][o]=='.';//cantrs条件2进一步判断
bool ischo[m];//每格是否1*2骨牌中的一格
for(int o=0;o<m;o++)ischo[o]=dgt[trs0][o]==1&&a[i-1][o]=='.'&&dgt[j][o]!=2;
for(int o=0;o<m;o++)if(ischo[o])//cantrs条件3
if(o+1<m&&ischo[o+1])ischo[o]=ischo[o+1]=false;
else ok=false;
if(ok)dp[i][j]=min(dp[i][j],dp[i-1][trs0]+cnt);//转移
}
}
int ans=inf;
for(int i=0;i<vld.size();i++){
bool ok=true;
bool ischo[m];//每格是否1*2骨牌中的一格
for(int j=0;j<m;j++)ischo[j]=dgt[i][j]==1&&a[n][j]=='.';
for(int j=0;j<m;j++)if(ischo[j])//vld条件4
if(j+1<m&&ischo[j+1])ischo[j]=ischo[j+1]=false;
else ok=false;
if(ok)ans=min(ans,dp[n][i]);//目标
}
cout<<ans/2;
return 0;
}
开开森森地交上去,什么???Time limit exceeded on test 10???再看一眼时限,\(250\mathrm{ms}\),原来是被卡常了。。于是,卡常时间到!
我当时先加了火车头,然后将某些在循环中定义的变量在外面定义,还在\(ok\)的判断中一发现为\(\mathrm{false}\)就break
掉,将状态转移方程中的\(cnt(i,j)\)提到\(\min\)外面,但这些都没什么卵用。真正的致命一击是:在判断每个转移对象是否合法之前,若此转移对象无法更新\(dp_{i,j}\),直接弃疗,continue
掉!这样就可以避免许多无用的判断,只用\(94\mathrm{ms}\)就获得了Accepted评测状态。
下面贴Accepted代码:
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=70,M=7;
int n/*字符矩阵行数*/,m/*字符矩阵列数*/;
char a[N+1][M+5];//字符矩阵
vector<int> vld;//vld筛出来的状态表
vector<vector<int> > dgt;//每个三进制数的每一位
vector<vector<int> > trs;//cantrs筛出来的转移表
vector<int> dp[N+1];//DP数组
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
int pow3=1;
for(int i=1;i<=m;i++)pow3*=3;
bool ok;
int dgt0[m];
for(int i=0;i<pow3;i++){//预处理dgt&第1波筛
int cpy=i;
for(int j=0;j<m;j++)dgt0[j]=cpy%3,cpy/=3;
ok=true;
for(int j=0;ok&&j+1<m;j++)ok&=dgt0[j]||dgt0[j+1];//vld条件1
if(ok)vld.pb(i),dgt.pb(vector<int>(dgt0,dgt0+m));
}
trs.resize(vld.size());
for(int i=0;i<vld.size();i++)for(int j=0;j<vld.size();j++){//第2波筛
ok=true;
for(int k=0;ok&&k<m;k++)ok&=(dgt[i][k]||dgt[j][k])/*cantrs条件1*/&&(dgt[i][k]!=2||dgt[j][k]==1)/*cantrs条件2*/;
if(ok)trs[i].pb(j);
}
for(int i=0;i<=n;i++)dp[i].resize(vld.size(),inf);
for(int i=0;i<vld.size();i++){//边界
ok=true;
int cnt=0;//放骨牌的格子的数量
for(int j=0;ok&&j<m;j++)ok&=dgt[i][j]!=2/*vld条件3*/&&(dgt[i][j]==1||a[1][j]=='.')/*vld条件2*/,cnt+=dgt[i][j]==1&&a[1][j]=='.';
if(ok)dp[1][i]=cnt;
}
bool ischo[m];//每格是否1*2骨牌中的一格
for(int i=2;i<=n;i++)for(int j=0;j<vld.size();j++){//开始DP
ok=true;
int cnt=0;//放骨牌的格子的数量
for(int k=0;ok&&k<m;k++)ok&=dgt[j][k]==1||a[i][k]=='.'/*vld条件2*/,cnt+=dgt[j][k]==1&&a[i][k]=='.'||dgt[j][k]==2;
if(!ok)continue;
for(int k=0;k<trs[j].size();k++){
int trs0=trs[j][k];
if(dp[i-1][trs0]>=dp[i][j])continue;//如果更新不了,直接弃疗
ok=true;
for(int o=0;ok&&o<m;o++)ok&=dgt[j][o]!=2||dgt[trs0][o]==1&&a[i-1][o]=='.';//cantrs条件2进一步判断
if(!ok)continue;
for(int o=0;o<m;o++)ischo[o]=dgt[trs0][o]==1&&a[i-1][o]=='.'&&dgt[j][o]!=2;
for(int o=0;ok&&o<m;o++)if(ischo[o])//cantrs条件3
if(o+1<m&&ischo[o+1])ischo[o]=ischo[o+1]=false;
else ok=false;
if(ok)dp[i][j]=dp[i-1][trs0];//转移
}
dp[i][j]+=cnt;
}
int ans=inf;
for(int i=0;i<vld.size();i++){
ok=true;
for(int j=0;j<m;j++)ischo[j]=dgt[i][j]==1&&a[n][j]=='.';
for(int j=0;ok&&j<m;j++)if(ischo[j])//vld条件4
if(j+1<m&&ischo[j+1])ischo[j]=ischo[j+1]=false;
else ok=false;
if(ok)ans=min(ans,dp[n][i]);//目标
}
cout<<ans/2;
return 0;
}
原文链接:https://www.cnblogs.com/ycx-akioi/p/SGU-132.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- kuangbin专题 专题一 简单搜索 棋盘问题 POJ - 1321 2019-08-16
- BZOJ1132: [POI2008]Tro(叉积 排序) 2018-07-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash