#include<bits/stdc++.h>
using namespace std;
#define in inline
#define ll long long
const int N=510,mod=1024523;

in int read()
{
    int w=0,r=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')r=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*r;
}

in ll get()
{
    char ch;
    cin>>ch;
    return ch=='A'?1:0;
}
ll f[3][N][N];
ll up[N],dn[N];
in ll plu(ll x,ll y)
{
    return x+y>=mod?x+y-mod:x+y;
}

in ll min_(ll x,ll y)
{
    return x<y?x:y;
}

in ll max_(ll x,ll y)
{
    return x>y?x:y;
}

int n,m;
int now;
int main()
{
//  freopen("pearl.in","r",stdin);
//  freopen("pearl.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)up[i]=get();
    for(int i=1;i<=m;i++)dn[i]=get();
//  for(int i=1;i<=n;i++)cout<<up[i]<<endl;
    f[0][0][0]=1;
    now=1;
    for(int k=1;k<=(n+m);k++)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                f[now][i][j]=0;
            }
        }
        for(int i=max_(0,k-m);i<=min_(n,k);i++)
        {
            for(int j=max_(0,k-m);j<=min_(n,k);j++)
            {
                if(i>0&&j>0&&up[i]==up[j])f[now][i][j]=plu(f[now][i][j],f[now^1][i-1][j-1]);
                if(i>0&&k-j>0&&up[i]==dn[k-j])f[now][i][j]=plu(f[now][i][j],f[now^1][i-1][j]);
                if(k-i>0&&k-j>0&&dn[k-i]==dn[k-j])f[now][i][j]=plu(f[now][i][j],f[now^1][i][j]);
                if(k-i>0&&j>0&&dn[k-i]==up[j])f[now][i][j]=plu(f[now][i][j],f[now^1][i][j-1]);
                
            }
        }
        now^=1;
    }
    cout<<f[now^1][n][n]<<endl;
    return 0;
}

学习黄学长的。。。

P1822管道取珠Accepted
记录信息
评测状态 Accepted
题目 P1822 管道取珠
递交时间 2016-01-08 20:25:26
代码语言 C++
评测机 ShadowShore
消耗时间 3199 ms
消耗内存 495692 KiB
评测时间 2016-01-08 20:25:35
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 495692 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 495692 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 495692 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 495692 KiB, score = 10
测试数据 #4: Accepted, time = 46 ms, mem = 495692 KiB, score = 10
测试数据 #5: Accepted, time = 218 ms, mem = 495692 KiB, score = 10
测试数据 #6: Accepted, time = 765 ms, mem = 495692 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 495692 KiB, score = 10
测试数据 #8: Accepted, time = 437 ms, mem = 495692 KiB, score = 10
测试数据 #9: Accepted, time = 1703 ms, mem = 495692 KiB, score = 10
Accepted, time = 3199 ms, mem = 495692 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define mod 1024523

using namespace std;

int f[500 + 2][500 + 2][500 + 2];
int n , m;
char s1[500 + 2] , s2[500 + 2];

inline void modify( int & a , int b )
{
a += b;
if( a >= mod ) a -= mod;
}

int main()
{
scanf( "%d %d" , &n , &m );
scanf( "%s" , s1 + 1 );
scanf( "%s" , s2 + 1 );
reverse( s1 + 1 , s1 + n + 1 );
reverse( s2 + 1 , s2 + m + 1 );
f[0][0][0] = 1;
for( register int i = 0 ; i <= n ; i++ )
for( register int j = 0 ; j <= m ; j++ )
for( register int k = 0 ; k <= n ; k++ )
{
register int l = i + j - k;
register int temp = f[i][j][k];
if( l < 0 || l > m ) continue;
if( s1[i + 1] == s1[k + 1] ) modify( f[i + 1][j][k + 1] , temp );
if( s1[i + 1] == s2[l + 1] ) modify( f[i + 1][j][k] , temp );
if( s1[k + 1] == s2[j + 1] ) modify( f[i][j + 1][k + 1] , temp );
if( s2[j + 1] == s2[l + 1] ) modify( f[i][j + 1][k] , temp );
}
cout << f[n][m][n] << endl;
return 0;
}