Codeforces Round #316 (Div. 2) E-白红宇的个人博客

Codeforces Round #316 (Div. 2) E

发布日期：2021-11-16 12:56:55 浏览次数：2 分类：技术文章

本文共 1238 字，大约阅读时间需要 4 分钟。

一个n*m的网格，每个格子有一个字符，你需要从左上角走到右下角（只能往下或往右走），让经过的字符连起来是回文串，问有多少种方案。

dp。dp(i,j,k)，表示从起点走到i行j列的格子，且对称的格子在第k行（列可以计算出来）的方案数，最后的答案是斜线对称轴的方案数的和。但是这样做会超内存，需要滚动数组压第一维变为i%2。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           using namespace std;#define ll long longconst int mod = 1000000007;char mp[510][510];int dp[2][510][510];int n,m;inline bool verrify(int a,int b,int c,int d){ if(a<1||a>n||b<1||b>m||c
           
            n||d
            
             m)return 0; return 1;}int main(){ cin>>n>>m; int mid = (n+m+2)>>1; for(int i=1;i<=n;i++){ scanf("%s",mp[i]+1); } if(mp[1][1]==mp[n][m]){ dp[1][1][n]=1; } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m&&(i+j)<=mid;j++){ if(i==1&&j==1)continue; for(int ii=i;ii<=n;ii++){ int jj=2+n+m-i-j-ii; if(jj
             
              m)continue; dp[i%2][j][ii]=0; if(mp[i][j]==mp[ii][jj]){ if(verrify(i-1,j,ii+1,jj))dp[i%2][j][ii]+=dp[(i-1)%2][j][ii+1]; dp[i%2][j][ii]%=mod; if(verrify(i-1,j,ii,jj+1))dp[i%2][j][ii]+=dp[(i-1)%2][j][ii]; dp[i%2][j][ii]%=mod; if(verrify(i,j-1,ii+1,jj))dp[i%2][j][ii]+=dp[i%2][j-1][ii+1]; dp[i%2][j][ii]%=mod; if(verrify(i,j-1,ii,jj+1))dp[i%2][j][ii]+=dp[i%2][j-1][ii]; dp[i%2][j][ii]%=mod; } if(i+j==mid){ ans+=dp[i%2][j][ii]; ans%=mod; } } } } cout<
              
               <

转载地址：https://blog.csdn.net/squee_spoon/article/details/47760013 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu 4372 Count the Buildings

下一篇：hdu 1085 Holding Bin-Laden Captive!

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章