对字符串s,多次询问,给你两个数L和R,问在字符串区间l到r的字串中,包含多少回文串。
#include <iostream> #include<queue> #include <cstring> #define IOS std::ios::sync_with_stdio(0) using namespace std; const int N =5003; int vis[N][N],pal[N][N]; int f[N][N]; string s; int n; int test(int a,int b){ if(a>=b) return 1; if(s[a]!=s[b]) return 0; if(vis[a][b]) return pal[a][b]; vis[a][b]=1; return pal[a][b]=test(a+1,b-1); } void solve(){ int i,j,tes; cin>>s>>tes; n=s.size(); s=" "+s; for(int i=1;i<=n;i++) f[i][i]=1; for(int i=1;i<=n-1;i++) f[i][i+1]=(s[i]==s[i+1]?3:2); for(i=n-2;i>=1;i--) for(j=i+2;j<=n;j++) f[i][j]=(f[i+1][j]+f[i][j-1]-f[i+1][j-1]+(test(i,j)?1:0)); while(tes--){ int x,y; cin>>x>>y; cout<<f[x][y]<<endl; } } signed main(){ IOS; solve(); }
标签:Palindromes,return,int,Number,vis,CF245H,include,pal From: https://www.cnblogs.com/towboa/p/17149980.html