首页 > 代码库 > codeforces159D - Palindrome pairs 二重DP

codeforces159D - Palindrome pairs 二重DP

2024-07-14 21:41:52   221人阅读

题意：给你一个字符串，问你其中不重叠的回文字串对有多少

解题思路：这题用到两种方法，不过其实是一个很巧妙的二重dp

1）暴力求解以i开头，j结尾的是否为回文，如果是，ans += sum[i-1]（ans 为答案， sum[i]为在  1 - i内回文串的个数--需要dp求解）

这里非常耗时，时间大约为  n^3 ,  跑出来为 830ms

解题代码：

 1 // File Name: 159d.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月30日 星期三 16时37分50秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 #define LL long long 27 char str[2005];28 LL sum[2004];29 int is(int a,int b)30 {31      int k = (a+b)/2;32      for(int i = a ;i <= k ;i ++ )33      {34          if(str[i] != str[b-i+a])35              return 0 ;36      }37      return 1;38 }39 int main(){40     scanf("%s",&str[1]);41     LL ans = 0 ; 42     int len =  strlen(&str[1]);43     sum[0] = 0 ;44     for(int i = 1 ;i <=len ;i ++)45     {46          for(int j = 1;j <= i ;j ++)47          {48             if(is(j,i))49             {50                ans += sum[j-1];51                sum[i] ++ ;52             }53          }54          sum[i] += sum[i-1];55     }56     printf("%I64d\n",ans);57     return 0;58 }
View Code

 

2） 这里在前面一种解法上又多了一次dp，因为我们知道了所有情况的以 i 结尾的回文串以后就可以快速求出所有以 i+1 结尾的回文串，所以这里再加一个dp

跑出来时间为  30ms  效率提高了 近30倍

解题代码：

 1 // File Name: 159d.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月30日 星期三 16时37分50秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 using namespace std;26 #define LL long long 27 char str[2005];28 LL sum[2004];29 LL tans[2004];30 int dp[2000][2000];31 int main(){32     scanf("%s",&str[1]);33     LL ans = 0 ; 34     int len =  strlen(&str[1]);35     memset(tans,0,sizeof(tans));36     for(int i = 1;i <= len ;i ++)37         dp[i][0] = 0; 38     sum[0] = 0 ;39     dp[1][1] = 1; 40     tans[1] = 1;41     sum[1] = 1; 42     for(int i = 2 ;i <=len ;i ++)43     {44          dp[i][1] = 1; 45          tans[i] = 1; 46          ans += sum[i-1];47          for(int j = 0;j <= tans[i-1];j ++)48          {49               if(str[i-dp[i-1][j]-1] == str[i])50               {51                  ans += sum[i-dp[i-1][j]-2];52                  tans[i] ++ ;53                  dp[i][tans[i]] = dp[i-1][j] + 2;54               }55          }56          sum[i] = sum[i-1] + tans[i];57     }58 //    printf("%I64d\n",tans[2]);59     printf("%I64d\n",ans);60     return 0;61 }
View Code

 


联系
我们