90pts WA on #3

#include<bits/stdc++.h>
using namespace std;
char s[505];
long long dp[505][505];
int main()
{
 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	string ss;
	cin>>ss;
	char qwerty;
	long long kkk,yuan;
	long long n=ss.size(),ll,rr;
	for(long long i=1;i<=n;i++){
		s[i]=ss[i-1];
		dp[i][i]=1;
	}
	for(long long i=1;i<=n;i++){
		for(long long j=i+1;j<=n;j++){
			dp[i][j]=1e9;
		}
	}
	for(long long k=2;k<=n;k++){
		for(long long l=1,r=k;r<=n;l++,r++){
			ll=rr=kkk=yuan=0;
			qwerty=s[l];
			dp[l][r]=1;
			for(long long i=l+1;i<=r;i++){
				if(s[i]!=qwerty and s[i-1]==qwerty){
					ll=i;
				}
				if(s[i]==qwerty and s[i-1]!=qwerty){
					rr=i-1;
					kkk+=dp[ll][rr];
					ll=rr=0;
				} 
			} 
			if(ll!=0){
				kkk+=dp[ll][r];
			}
			if(s[l]==s[r]){
				ll=l,rr=r;
				while(ll<=rr){
					if(s[ll]==s[rr] and s[ll]==qwerty){
						ll++;
						rr--;
					}
					else{
						break;
					}
				}
				yuan=dp[ll][rr]; 
			}
			else{
				yuan=1e9;
			}
			dp[l][r]+=min(kkk,yuan);
			for(long long i=l;i<r;i++){
				dp[l][r]=min(dp[l][r],dp[l][i]+dp[i+1][r]);
			} 
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}

差不多把所有的贴的hack都试了遍