openjudge 百练 4122 切割回文

2023-09-24 12 0

题目:切割回文

思路:
O(n^2)处理回文串,转移方程:

if(a[j]==a[i]&&b[i+1][j-1]) b[i][j]=true; 
else b[i][j]=false;

O(n^2)处理最小分割次数。f[i]表示前i个字符最少分为几段。
转移方程:

if(b[j][i]) f[i]=min(f[i],f[j-1]+1);

代码:

#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 1000int T;
int n;
char a[maxn+5];
bool b[maxn+5][maxn+5];
int f[maxn+5];void mk() {for(int i=n;i>=1;i--) {b[i][i]=true;if(a[i]==a[i+1]) b[i][i+1]=true;for(int j=i+2;j<=n;j++) {if(a[j]==a[i]&&b[i+1][j-1]) b[i][j]=true; }}
}void init() {memset(b,0,sizeof(b));for(int i=1;i<=n;i++) f[i]=1e9;
}int dp() {for(int i=1;i<=n;i++) {for(int j=1;j<=i;j++) {if(b[j][i]) f[i]=min(f[i],f[j-1]+1);}}return f[n];
}int main() {read(T);while(T--) {scanf("%s",a+1);n=strlen(a+1);init();mk();int ans=dp()-1;printf("%d\n",ans);}return 0;
}
代码编程
赞赏

相关文章

idea中使用git查修改了哪些代码文件
idea的插件:Free Mybatis plugin
SQLServer使用
请不要尝试简化这些代码!保持航天飞机风格
An enum switch case label must be the unqualified name of an enumeration constant
An incompatible version [1.1.32] of the APR based Apache Tomcat Native library is installed