学习黄学长的。。。

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;
}