Cerinta completa

Steve loves playing with palindromes. He has a string, , consisting of lowercase English alphabetic characters (i.e., a through z). He wants to calculate the number of ways to insert exactly lowercase character into string such that the length of the longest palindromic subsequence of increases by at least . Two ways are considered to be different if either of the following conditions are satisfied:

  • The positions of insertion are different.
  • The inserted characters are different.

This means there are at most different ways to insert exactly character into a string of length .

Given queries consisting of , , and , print the number of different ways of inserting exactly new lowercase letter into string such that the length of the longest palindromic subsequence of increases by at least .

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line of a query contains two space-separated integers denoting the respective values of and .
  2. The second line contains a single string denoting .

Constraints

  • It is guaranteed that consists of lowercase English alphabetic letters (i.e., a to z) only.

Subtasks

  • for of the maximum score.
  • for of the maximum score.

Output Format

On a new line for each query, print the number of ways to insert exactly new lowercase letter into string such that the length of the longest palindromic subsequence of increases by at least .

Sample Input

3
1 1
a
3 2
aab
3 0
aba

Sample Output

2
1
104

Explanation

We perform the following queries:

  1. The length of the longest palindromic subsequence of a is . There are two ways to increase this string’s length by at least :

    1. Insert an a at the start of string , making it aa.
    2. Insert an a at the end of string , making it aa.

    Both methods result in aa, which has a longest palindromic subsequence of length (which is longer than the original longest palindromic subsequence’s length by ). Because there are two such ways, we print on a new line.

  2. The length of the longest palindromic subsequence of aab is . There is one way to increase the length by at least :

    1. Insert a b at the start of string , making it baab.

    We only have one possible string, baab, and the length of its longest palindromic subsequence is (which is longer than the original longest palindromic subsequence’s length by ). Because there is one such way, we print on a new line.

Limbajul de programare folosit: cpp20

Cod:

#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 3005;
int dp[SIZE][SIZE];
int dp2[SIZE][SIZE];
char s[SIZE];
int main(){
    CASET{
        DRII(n,K);
        RS(s+1);
        if(K>2)puts("0");
        else if(K==0){
            printf("%d\n",n*26+26);
        }
        else{
            MS0(dp);
            MS0(dp2);
            REPP(i,1,n+1)dp2[i][i]=1;
            REPP(j,1,n){
                for(int k=1;k+j<=n;k++){
                    int ll=k,rr=k+j;
                    if(s[ll]==s[rr])dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr-1]+2);
                    dp2[ll][rr]=max(dp2[ll][rr],dp2[ll+1][rr]);
                    dp2[ll][rr]=max(dp2[ll][rr],dp2[ll][rr-1]);
                }
            }
            int ma=0;
            for(int i=1;i<n;i++){
                for(int j=n;j>i;j--){
                    if(s[i]==s[j])dp[i][j]=dp[i-1][j+1]+2;
                    else dp[i][j]=max(dp[i-1][j],dp[i][j+1]);
                    ma=max(ma,dp[i][j]);
                }
            }
            REPP(i,1,n+1)ma=max(ma,dp[i-1][i+1]+1);
            int an=0;
            REP(i,n+1){
                int me=0;
                me=dp[i][i+1]+1;
                if(me>=ma+K){
                    an+=26;
                    continue;
                }
                bool used[26]={};
                REPP(j,1,n+1){
                    if(j<=i){
                        if(dp2[j+1][i]+dp[j-1][i+1]+2>=ma+K)used[s[j]-'a']=1;
                    }
                    else{
                        if(dp2[i+1][j-1]+dp[i][j+1]+2>=ma+K)used[s[j]-'a']=1;
                    }
                }
                REP(j,26)
                    if(used[j]){
                        an++;
                    }
            }
            printf("%d\n",an);
        }
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464640439

Link challenge: https://www.hackerrank.com/challenges/longest-palindromic-subsequence/problem

Longest Palindromic Subsequence