hdu 4632 区间DP

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define mod 10007
 6 
 7 char str[1005];
 8 int dp[1005][1005];
 9 
10 int main()
11 {
12     int t,cs=1;
13     scanf("%d",&t);
14     while(t--){
15         scanf("%s",str);
16         int len=strlen(str);
17         memset(dp,0,sizeof(dp));
18         for(int i=0;i<len;i++)
19             dp[i][i]=1;
20         for(int i=1;i<len;i++)
21             for(int j=i-1;j>=0;j--)
22             {
23                 dp[j][i]=(dp[j][i-1]+dp[j+1][i]-dp[j+1][i-1]+mod)%mod;// 前面部分+后面部分-重叠部分，+mod的原因是每次计算都是先计算该值的右面取余，再计算该值的下面部分取余，再减去重叠部分的值，有可能右面部分%mod+下面部分%mod-重叠部分的值会是一个负数，所以要先加mod,然后再取余
24                 if(str[i]==str[j])
25                     dp[j][i]=(dp[j][i]+dp[j+1][i-1]+1+mod)%mod;
26             }
27         printf("Case %d: %d\n",cs++,dp[0][len-1]);
28     }
29     return 0;
30 }