Cod sursa(job #1596470)

Utilizator tudi98Cozma Tudor tudi98 Data 11 februarie 2016 00:29:40
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
using namespace std;

string s;
int dp[505][505][26];   // dp[i][j][k] = cel mai lung subsir care are mijlocul in i,j cu literele din mijloc k

int main()
{
    ifstream fin("palm.in");
    ofstream fout("palm.out");

    fin >> s;

    int n = s.size();
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= i; j--)
            for (int k = 0; k < 26; k++)
            {
                if (dp[i-1][j][k] > dp[i][j+1][k]) dp[i][j][k] = dp[i-1][j][k];
                else dp[i][j][k] = dp[i][j+1][k];

                if (dp[i][j][k-1] > dp[i][j][k]) dp[i][j][k] = dp[i][j][k-1];

                if (s[i-1] == s[j-1] && s[i-1]-'a' == k && dp[i-1][j+1][k] + 1 > dp[i][j][k])
                    dp[i][j][k] = dp[i-1][j+1][k] + 1;
            }

    int Sol = 0;
    for (int i = 1; i <= n; i++) {
        Sol = max(Sol,dp[i][i][s[i-1]-'a']*2-1);
        Sol = max(Sol,dp[i][i+1][s[i-1]-'a']*2);
    }

    fout << Sol;
}