Cod sursa(job #3170552)

Utilizator divadddDavid Curca divaddd Data 17 noiembrie 2023 19:13:31
Problema Iv Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 502;
int n,m,dp[NMAX][NMAX][NMAX];
string a,b;

ifstream fin("iv.in");
ofstream fout("iv.out");

int main()
{
    fin >> a >> b;
    n = a.size(), m = b.size();
    a = "$"+a;
    b = "$"+b;
    dp[0][0][0] = 1;
    int half = (n+m)/2;
    for(int i = 1; i <= (n+m)/2; i++){
        for(int p1 = 0; p1 <= n && p1 <= i; p1++){
            for(int q1 = 0; p1+q1 <= n && q1 <= i; q1++){
                int p2 = i-p1;
                int q2 = i-q1;
                if(a[p1] == a[n-q1+1]){
                    dp[i][p1][q1] += dp[i-1][p1-1][q1-1];
                }
                if(a[p1] == b[m-q2+1]){
                    dp[i][p1][q1] += dp[i-1][p1-1][q1];
                }
                if(b[p2] == a[n-q1+1]){
                    dp[i][p1][q1] += dp[i-1][p1][q1-1];
                }
                if(b[p2] ==  b[m-q2+1]){
                    dp[i][p1][q1] += dp[i-1][p1][q1];
                }
            }
        }
    }
    int ans = 0;
    if((n+m)%2 == 0){
        for(int i = 0; i <= n; i++){
            ans += dp[half][i][n-i];
        }
    }else{
        for(int i = 0; i <= n; i++){
            ans += dp[half][i][n-i-1] + dp[half][i][n-i];
        }
    }
    fout << ans;
    return 0;
}