首页 > 代码库 > codeforces159D - Palindrome pairs 二重DP
codeforces159D - Palindrome pairs 二重DP
题意:给你一个字符串,问你其中不重叠的回文字串对有多少
解题思路:这题用到两种方法,不过其实是一个很巧妙的二重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 }
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。