Jinnie

显然的线性dp

预处理谁是回文串就可以了

#include
#include
#include
#include
#include
using namespace std;
int all[1005][1005];
string s;
int t;
int l;
int f[100001];
char ss[10001];
void che(int x){
    int ll=x;
    int r=x;
    while(ll>=1&&r<=l){
        if(ss[ll]==ss[r]){
            all[ll][r]=1;
        }else{
            break;
        }
        ll--;
        r++;
    }
    ll=x;
    r=x+1;
    while(ll>0&&r<=l){
        if(ss[ll]==ss[r]){
            all[ll][r]=1;
        }else{
            break;
        }
        ll--;
        r++;
    }
}
int main(){
     scanf("%d",&t);
    while(t--){
        cin>>s;
        l=s.length();
        for(int i=1;i<=l;++i){
            ss[i]=s[i-1];
        }
        memset(all,0,sizeof(all));
        memset(f,0x7f,sizeof(f));
        for(int i=1;i<=l;++i){
            che(i);
        }
        f[0]=0;
        for(int i=1;i<=l;++i){
            for(int j=0;j