动态规划：NOI 2009 管道取珠

[NOI2009] 管道取珠

输入文件：ballb.in   输出文件：ballb.out   简单对比
时间限制：1 s  
内存限制：512 MB

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 const int mod=;

 char A[maxn],B[maxn];

 int dp[maxn][maxn][maxn];

 int n,m;

 int main(){

     freopen("ballb.in","r",stdin);

     freopen("ballb.out","w",stdout);

     scanf("%d%d",&n,&m);

     scanf("%s%s",A+,B+);

     dp[][][]=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             for(int k=max(i+j-m,);k<=i+j;k++){

                 if(!i&&!j&&!k)continue;

                 int l=i+j-k;

                 if(A[i]==A[k]&&i&&k)dp[i][j][k]+=dp[i-][j][k-];

                 if(A[i]==B[l]&&i&&l)dp[i][j][k]+=dp[i-][j][k];

                 if(B[j]==A[k]&&j&&k)dp[i][j][k]+=dp[i][j-][k-];

                 if(B[j]==B[l]&&j&&l)dp[i][j][k]+=dp[i][j-][k];

                 dp[i][j][k]%=mod;

             }

     printf("%d\n",dp[n][m][n]);

     return ;

 }

　　最开始想如果不平方，求结果不同的方案个数，发现几乎无法实现。

　　这里有平方，就可以这样转化：把每种方案复制一遍，然后配对，只有相同才计入答案，简单地DP一下就解决了。