90分求调
查看原帖
90分求调
1183074
xzy_AK_IOI楼主2025/1/20 16:55
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,k,n) for (int i=k;i<=n;i++)
const int N=100;
typedef long long ll;
string s;
int n;
int a[N],dp[N][N];
signed main(){
	cin>>s;
	memset(dp,0x3f,sizeof dp);
	n=s.size();
	F(i,1,n) a[i]=s[i-1];
	F(i,1,n) dp[i][i]=1;
	F(len,2,n){
		F(l,1,n){
			int r=l+len-1;
			if (r>n) break;
			int nl=l,nr=r;
			if (a[l]==a[r]){
				while (nl<=r && a[nl]==a[r]) nl++;
				while (nr>=l && a[nr]==a[l]) nr--;
				if (nl>nr){
					dp[l][r]=1;
					continue;
				} 
				dp[l][r]=dp[nl][nr]+1;
			}
			F(k,l,r-1){
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
				if (a[l]==a[k] && a[k]==a[r]){//cout<<l<<' '<<r<<"dfsdlfsd\n";
					int nkl=k,nkr=k;
					while (nkl>nl && a[k]==a[nkl]) nkl--;
					while (nkr<nr && a[k]==a[nkr]) nkr++;
					dp[l][r]=min(dp[l][r],dp[nl][nkl]+dp[nkr][nr]+1);//cout<<nkl<<' '<<nkr<<'\n';
				}
			}
			//cout<<l<<' '<<r<<' '<<dp[l][r]<<' '<<nl<<' '<<nr<<'\n';
		}
	}
	cout<<dp[1][n];
	return 0;
}
/*
abacbca
*/
2025/1/20 16:55
加载中...