c/c++语言开发共享SGU 132 Another Chocolate Maniac

codeforces题目页面传送门

给定一个(ntimes m)的字符矩阵，每个字符是(texttt.)或(texttt*)，分别表示空格和障碍物。在这个字符矩阵上放若干个(1times2)或(2times1)的骨牌，求最少放多少个使得没有空地再放。

(nin[1,70],min[1,7])。

看到(m)如此之小，很容易想到对最终状态的每行进行装压，然后再以行数作为阶段dp。

考虑最终状态有多少种格子，给每种分配一个编号状压。显而易见的有空格、障碍物和骨牌中的一格。因为如果一个格子在给定字符矩阵的时候是障碍物，那么它在最终形态中就必须是障碍物，相反，如果给定的时候不是障碍物，那么它在最终状态中也不可能是障碍物，所以不需要专门给障碍物设一个编号，让它随便和另一种状态用同一个编号即可，放到具体某行某列中自能识别是否障碍物。对于骨牌中的一格，由于它是(1times2)还是(2times1)的骨牌中的一格在向相邻行转移时情况是不一样的，所以要分出(3)种：(1times2)骨牌中的一格、(2times1)骨牌中的上格、(2times1)骨牌中的下格。而在转移时，(2times1)骨牌中的上下格是必须匹配的，所以又可以省去一个编号。于是编号就确定了：(0)：空格，(1)：(1times2)骨牌中的一格或(2times1)骨牌中的上格，(2)：(2times1)骨牌中的下格。至于障碍物到底跟谁共享编号，到下面再讨论。

接下来可以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}minlimits_{cantrs(i,j,k)}{dp_{i-1,k}+cnt(i,j)}&vld(i,j)\infty&lnot vld(i,j)end{cases})，目标为(dfrac{minlimits_{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})当且仅当满足以下全部条件：

1. (j)中没有相邻的空格；
2. 第(i)行所有障碍物的格子在(j)中全是障碍物的编号；
3. 如果(i=1)，那么(j)中没有(1times2)骨牌中的下格；
4. 如果(i=n)，那么(j)中所有(1times2)骨牌中的一格组成的连续段长度都要是偶数。（这一条本来是要放到(cantrs)里判的，因为要根据下面一排哪些地方是(2times1)骨牌中的下格才能知道本排所有编号为(1)的格子分别是是(2times1)骨牌中的上格还是(1times2)骨牌中的一格，才好做判断。但是第(n)排并没有下面一排，所以可以确定不存在(2times1)骨牌中的上格，又在(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^2nmapprox 7times10^8)次运算，过不去。于是继续优化。

再来考虑(cantrs)的判断方法：(cantrs_{i,j,k})当且仅当满足以下全部条件：

1. (j,k)中没有纵相邻的空格；
2. 对于所有(j)中是(2times1)骨牌中的下格的位置，(k)中此位置是(2times1)骨牌中的上格；
3. (k)中所有(1times2)骨牌中的一格组成的连续段长度都要是偶数。（因为要根据下面一排哪些地方是(2times1)骨牌中的下格才能知道本排所有编号为(1)的格子分别是是(2times1)骨牌中的上格还是(1times2)骨牌中的一格，才好做判断，所以拿到(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)的格子是否(1times2)的骨牌，也就是说第(3)条与(i)有关了，于是不能列入预先筛的条件。如此又筛过一波后，经计算，当(m=7)时会筛出来(129318)个转移对，从(1224^2=1498176)个原有的转移对中筛掉了(dfrac1{10})还多！！现在当(n=70,m=7)时最多要做约(129318nmapprox6times10^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¿¿¿再看一眼时限，(250mathrm{ms})，原来是被卡常了。。于是，卡常时间到！

我当时先加了火车头，然后将某些在循环中定义的变量在外面定义，还在(ok)的判断中一发现为(mathrm{false})就break掉，将状态转移方程中的(cnt(i,j))提到(min)外面，但这些都没什么卵用。真正的致命一击是：在判断每个转移对象是否合法之前，若此转移对象无法更新(dp_{i,j})，直接弃疗，continue掉！这样就可以避免许多无用的判断，只用(94mathrm{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; }