网友投稿 500 2022-11-10
Light oj 1044 - Palindrome Partitioning （多校连萌，求最少回文子串的个数）
题目地址：#include #include #include #include #include #include #include #include #include #include const int inf = 0x3f3f3f3f;//1061109567typedef long long LL;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;char a[1010];int visit[1010][1010],dp[1010];int check(int st,int ed){ if(visit[st][ed] != -1) return visit[st][ed]; if(st > ed) return visit[st][ed] = 1; if(a[st] != a[ed]) return visit[st][ed] = 0; return visit[st][ed] = check(st+1,ed-1);}int main(){ int t,cas = 1; scanf("%d",&t); while(t--) { memset(visit,-1,sizeof(visit)); memset(dp,0,sizeof(dp)); scanf("%s",a+1); int len = strlen(a+1); for(int i=1; i<=len; i++) { dp[i] = dp[i-1] + 1; for(int j=i-1; j>=1; j--) { if(a[i] == a[j] && check(j,i)) dp[i] = min(dp[i],dp[j-1]+1);//后面一个的意思是前面j-1个的数量加上1，1表示j到i是一个回文串 } } printf("Case %d: %d\n",cas++,dp[len]); } return 0;}
版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论，来抢沙发吧~
暂时没有评论，来抢沙发吧~