P7668 [JOI2018] Dango Maker

Solution

我们可以把一个符合要求的团子记录在中间那个 G 中，那么两个团子可能冲突，只有可能当前 G 竖着可以横着也可以，或者说两个或多个 G 在同一条 右上-左下 的对角线上。

如图，只有这两种情况会冲突，当然两种情况也有可能重叠。

于是我们把所有符合要求的 右上-左下 对角线的所有 G 全抠出来做 dp，最后合并答案即可。

设 \(f(i,0/1/2)\) 表示每个 G 不选、横选、竖选，线性做一遍就没了。时间复杂度 \(O(nm)\)。

Code

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using ull=unsigned long long;
inline void read(int &x){
  char ch=getchar();
  int r=0,w=1;
  while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
  while(isdigit(ch))r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
  x=r*w;
}
const int N=3007,inf=1e9;
int n,m,f[N][3],tot,ans;
char c[N][N];
struct node{
  bool ok1,ok2;
}a[N][N],b[N];
bool used[N][N];
int dp(int n){
  // printf("debug n:%d\n",n);
  for(int i=1;i<=n;i++)f[i][0]=f[i][1]=f[i][2]=-inf;
  f[1][0]=0;f[1][1]=b[1].ok1?1:-inf;f[1][2]=b[1].ok2?1:-inf;
  for(int i=2;i<=n;i++){
    f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
    if(b[i].ok1)f[i][1]=max(f[i-1][0],f[i-1][1])+1;
    if(b[i].ok2)f[i][2]=max(f[i-1][0],f[i-1][2])+1;
  }
  return max({f[n][0],f[n][1],f[n][2]});
}
int main(){
  read(n);read(m);
  for(int i=1;i<=n;i++)scanf("%s",c[i]+1);
  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    if(c[i][j]=='G'&&c[i][j-1]=='R'&&c[i][j+1]=='W')a[i][j].ok1=1;
    if(c[i][j]=='G'&&c[i-1][j]=='R'&&c[i+1][j]=='W')a[i][j].ok2=1;
  }
  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    tot=0;
    int x=i,y=j;
    while((a[x][y].ok1||a[x][y].ok2)&&x>0&&x<=n&&y>0&&y<=m&&!used[x][y])
      b[++tot]=a[x][y],used[x][y]=1,x++,y--;
    if(tot)ans+=dp(tot);
  }
  cout<<ans;
  return 0;
}