首页 > 代码库 > 【uva-11584】Partitioning by Palindromes(dp)
【uva-11584】Partitioning by Palindromes(dp)
粗略的复杂度是L^3,长度最大是1000,,没敢做,之后发现其实这个复杂度的系数也不大,可以过,而且很快。
dp[j] = dp[i - 1] + 1 (if(str[i] ~ str[j]为回文)
14327451 | 11584 | Partitioning by Palindromes | Accepted | C++ | 0.052 | 2014-10-09 09:33:17 |
#include<set> #include<map> #include<stack> #include<queue> #include<vector> #include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; const int maxn = 1111; char str[maxn]; int dp[maxn]; bool is_part(int i,int j){ while(i < j){ if(str[i] != str[j]) return false; i ++; j --; } return true; } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%s",str); int L = strlen(str); for(int i = 0 ; i <= L; i ++) dp[i] = i + 1; for(int j = 0 ; j < L; j ++) // L for(int i = 0 ; i <= j ; i ++){ // L if(is_part(i,j)){ // L if(i - 1 >= 0) dp[j] = min(dp[j],dp[i - 1] + 1); else dp[j] = 1; } } printf("%d\n",dp[L - 1]); } return 0; }
【uva-11584】Partitioning by Palindromes(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。