「模拟8.23」阴阳 DP

对于此题的性质我们考虑DP

分四种情况

黑色块在右侧单调降，单调升

还有在左侧

另外我们这样可能会记重，所以还要将重复记过的也就是边界线是横的和竖的

然后还要将全白全黑加上

  1 #include<bits/stdc++.h>
  2 #define MAXN 2100
  3 #define int long long
  4 using namespace std;
  5 int f[5][MAXN][MAXN];
  6 int sum[5][MAXN][MAXN];
  7 int n,m;
  8 const int mod=1e9+7;
  9 char c[MAXN][MAXN];
 10 int jud[2][MAXN][MAXN];
 11 int jud_sum[2][MAXN][MAXN];
 12 void work(int k,int cal)
 13 {    
 14     f[k][0][m]=1;
 15     for(int i=1;i<=n;++i)//黑色单降靠左
 16     {
 17         sum[k][i-1][m]=f[k][i-1][m];
 18         for(int j=m-1;j>=0;--j)
 19         {
 20            sum[k][i-1][j]=(sum[k][i-1][j+1]+f[k][i-1][j])%mod;
 21            //printf("sum[%lld][%lld][%lld]=%lld\n",k,i-1,j,sum[k][i-1][j]);
 22         }
 23         for(int j=0;j<=m;++j)
 24         {  
 25             //printf("i%lld j=%lld jud%lld %lld\n",i,j,jud[cal][i][j],(jud[cal^1][i][m]-jud[cal^1][i][j]));
 26             if(j!=0)
 27                 if(jud[cal][i][j]!=0||(jud[cal^1][i][m]-jud[cal^1][i][j])!=0){continue;}
 28             if(j==0)
 29                 if(jud[cal][i][j]||jud[cal^1][i][m]){continue;}
 30                 f[k][i][j]=sum[k][i-1][j]%mod;
 31             //printf("f[%lld][%lld][%lld]=%lld\n",k,i,j,f[k][i][j]);
 32         }
 33     }
 34     f[k+1][0][0]=1;
 35     for(int i=1;i<=n;++i)//黑色单升靠左
 36     {
 37         sum[k+1][i-1][0]=f[k+1][i-1][0];
 38         for(int j=1;j<=m;++j)
 39         {
 40            sum[k+1][i-1][j]=(sum[k+1][i-1][j-1]+f[k+1][i-1][j])%mod;
 41         }
 42         for(int j=0;j<=m;++j)
 43         {  
 44             if(j)
 45                 if(jud[cal][i][j]||(jud[cal^1][i][m]-jud[cal^1][i][j]))continue;
 46             if(j==0)
 47                 if(jud[cal][i][j]||jud[cal^1][i][m])continue;
 48             f[k+1][i][j]=sum[k+1][i-1][j]%mod;
 49             //printf("f[%lld][%lld][%lld]=%lld\n",k+1,i,j,f[k+1][i][j]);
 50         }
 51     }
 52 }
 53 int ans=0;
 54 int get_sum(int k,int x1,int y1,int x2,int y2)
 55 {
 56     if(x1>x2)return 0;if(y1>y2)return 0;
 57     return (jud_sum[k][x2][y2]-jud_sum[k][x1-1][y2]-jud_sum[k][x2][y1-1]+jud_sum[k][x1-1][y1-1]+mod)%mod;
 58 }
 59 void work2()
 60 {
 61      for(int i=0;i<=n;++i)
 62      {
 63          if(get_sum(1,1,1,i,m)==0&&get_sum(0,i+1,1,n,m)==0)
 64          {
 65              ans--;
 66          }
 67      }
 68      for(int i=0;i<=n;++i)
 69      {
 70          if(get_sum(0,1,1,i,m)==0&&get_sum(1,i+1,1,n,m)==0)
 71          {
 72              ans--;
 73          }
 74      }
 75      for(int i=0;i<=m;++i)
 76      {
 77          if(get_sum(0,1,1,n,i)==0&&get_sum(1,1,i+1,n,m)==0)
 78          {
 79              ans--;
 80          }
 81      }
 82      for(int i=0;i<=m;++i)
 83      {
 84          if(get_sum(1,1,1,n,i)==0&&get_sum(0,1,i+1,n,m)==0)
 85          {
 86              ans--;
 87          }
 88      }     
 89      if(get_sum(1,1,1,n,m)==0)ans++;
 90      if(get_sum(0,1,1,n,m)==0)ans++;
 91 }
 92 signed main()
 93 {
 94     scanf("%lld%lld",&n,&m);
 95     for(int i=1;i<=n;++i)
 96     {
 97         scanf("%s",c[i]+1);
 98         for(int j=1;j<=m;++j)
 99         {
100             jud[0][i][j]+=jud[0][i][j-1];
101             jud[1][i][j]+=jud[1][i][j-1];
102             jud_sum[0][i][j]=(jud_sum[0][i-1][j]+jud_sum[0][i][j-1]-jud_sum[0][i-1][j-1])%mod;
103             jud_sum[1][i][j]=(jud_sum[1][i-1][j]+jud_sum[1][i][j-1]-jud_sum[1][i-1][j-1])%mod;            
104             if(c[i][j]==‘B‘){jud[0][i][j]++;jud_sum[0][i][j]++;}
105             if(c[i][j]==‘W‘){jud[1][i][j]++;jud_sum[1][i][j]++;}
106         }
107     }
108     work(1,1);
109     work(3,0);
110     for(int k=1;k<=4;++k)
111     {
112         for(int i=0;i<=m;++i)
113         {
114             ans=(ans+f[k][n][i])%mod;
115             //printf("f[%lld][%lld][%lld]=%lld\n",k,n,i,f[k][n][i]);
116         }
117     }
118     //printf("初ans=%lld\n",ans);
119     work2();
120     printf("%lld\n",ans%mod);
121 }

View Code