CROC-MBTU 2012, Elimination Round (ACM-ICPC) H DP题目-白红宇

CROC-MBTU 2012, Elimination Round (ACM-ICPC) H DP题目

阅读量：4604 次

发布时间：2019-06-09

本文共 1502 字，大约阅读时间需要 5 分钟。

题意：

给定一个字符串s (1 ≤ |s| ≤ 5000) 然后又q个询问(1 ≤ q ≤ 10⁶) 每次询问包括两个数l,r 求l到r内回文串的个数。

思路：

自己对dp的感觉真是弱爆了，大牛们16分钟就能A出来的题目，自己想了好久还是没思路，最后看了别人的代码才AC的，弱爆了。

dp[i][j] = d[i][j -1] + dp[i + 1][j] - dp[i + 1][j - 1] - R[i][j] 这里R[i][j]表示子串s[i...j]是否是回文串，这里的处理太棒了，自己没能想到。还有就是转移方程也没想到真是弱爆了。还是要继续加油啊。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define CL(a,num) memset((a),(num),sizeof(a))#define iabs(x) ((x) > 0 ? (x) : -(x))#define Min(a,b) (a) > (b)? (b):(a)#define Max(a,b) (a) > (b)? (a):(b)#define ll long long#define inf 0x7f7f7f7f#define MOD 1073741824#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define test puts("<------------------->")#define maxn 100007#define M 107#define N 5007using namespace std;//freopen("din.txt","r",stdin);int dp[N][N],R[N][N];char s[N];int n;int main(){ //freopen("din.txt","r",stdin); int q,l,r; int i,j; scanf("%s",s + 1); n = strlen(s + 1); CL(dp,0); CL(R,0); for (i = 1; i <= n; ++i) R[i][i] = R[i + 1][i] = dp[i][i] = 1; for (i = 2; i <= n; ++i)//从长度小的开始处理 { for (j = 1; j <= n; ++j) { int k = j + i - 1; R[j][k] = R[j + 1][k - 1]&&(s[j] == s[k]); dp[j][k] = dp[j + 1][k] + dp[j][k - 1] - dp[j + 1][k - 1] + R[j][k]; } } scanf("%d",&q); while (q--) { scanf("%d%d",&l,&r); printf("%d\n",dp[l][r]); } return 0;}

转载于:https://www.cnblogs.com/E-star/archive/2012/11/21/2781477.html

你可能感兴趣的文章