Cod sursa(job #833756)

Utilizator elfusFlorin Chirica elfus Data 12 decembrie 2012 23:51:22
Problema Iv Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <string.h>

int N, M, dp[210][210][210];
char x[510], y[510];

int isNull(int x)
{
	if (x == 0)
		return -1;
	return x;
}

int solve(int x0, int y0, int x1)
{
	int y1 = x0 - 1 + x1 - 1 - N + y0;
	y1 = M - y1;
	
	if (dp[x0][y0][x1] != -1)
		return dp[x0][y0][x1];
	if (x0 > y0 || x1 > y1)
		return 1;
	
	int ret = 0;
	
	if (x[x0] == x[y0])
		ret += solve(x0 + 1, y0 - 1, x1);
	if (x[x0] == y[y1])
		ret += solve(x0 + 1, y0, x1);
	if (y[x1] == x[y0])
		ret += solve(x0, y0 - 1, x1 + 1);
	if (y[x1] == y[y1])
		ret += solve(x0, y0, x1 + 1);
	
	return dp[x0][y0][x1] = ret;
}

int main()
{
	int i, j, k;
	
	freopen("iv.in", "r", stdin);
	freopen("iv.out", "w", stdout);
	
	gets(x + 1); gets(y + 1);
	N = strlen(x + 1); M = strlen(y + 1);
	
	for (i = 0; i <= N; i ++)
		for (j = 0; j <= N; j ++)
			for (k = 0; k <= M; k ++)
				dp[i][j][k] = -1;
	
	printf("%d", solve(1, N, 1));
	return 0;
}