「模拟8.23」阴阳 DP_C

概述对于此题的性质我们考虑DP 分四种情况黑色块在右侧单调降，单调升还有在左侧另外我们这样可能会记重，所以还要将重复记过的也就是边界线是横的和竖的然后还要将全白全黑加上 1 #include<bits/stdc++.h> 2 #define MAXN 2100 3 #define int long long 4 using namespace std; 5 int

对于此题的性质我们考虑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,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",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,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,m)==0&&get_sum(0,i+1,n,m)==0) 64          { 65              ans--; 66          } 67      } 68      for(int i=0;i<=n;++i) 69      { 70          if(get_sum(0,m)==0&&get_sum(1,m)==0) 71          { 72              ans--; 73          } 74      } 75      for(int i=0;i<=m;++i) 76      { 77          if(get_sum(0,i)==0&&get_sum(1,m)==0) 78          { 79              ans--; 80          } 81      } 82      for(int i=0;i<=m;++i) 83      { 84          if(get_sum(1,i)==0&&get_sum(0,m)==0) 85          { 86              ans--; 87          } 88      }      89      if(get_sum(1,m)==0)ans++; 90      if(get_sum(0,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",f[k][n][i]);116         }117     }118     //printf("初ans=%lld\n",ans);119     work2();120     printf("%lld\n",ans%mod);121 }