問題
http://topcoder.bgcoder.com/print.php?id=1160
A~Zからなる文字列がある。
これをサブ文字列に分割して各サブ文字列が回文になるようにしたい。
このときの最小のサブ文字列の数を求める。
解き方
２段階でｄｐを適用する。
最初は各文字について、そこからどの長さまで回文になるかをｄｐで求める。
最後に、そのｄｐを使って最小のサブ文字列の数を求める。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int can[2501][2501];
class PalindromePartition {
public:
int partition(vector<string> s) {
string str="";
FORE(i,0,s.size())str+=s[i];
int n=str.size();
memset(can,0,sizeof(can));
FORE(i,0,n)can[i][1]=1;
FORE(i,0,n-1)can[i][2]=(str[i]==str[i+1]);
FORE(len,3,n+1)FORE(i,0,n-len+1){
can[i][len]=(str[i]==str[i+len-1] && can[i+1][len-2] );
}
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,n+1)FORE(j,1,i+1){
if(can[i-j][j])dp[i]=min(dp[i],dp[i-j]+1);
}
return dp[n];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int can[2501][2501];
class PalindromePartition {
public:
int partition(vector<string> s) {
string str="";
FORE(i,0,s.size())str+=s[i];
int n=str.size();
memset(can,0,sizeof(can));
FORE(i,0,n)can[i][1]=1;
FORE(i,0,n-1)can[i][2]=(str[i]==str[i+1]);
FORE(len,3,n+1)FORE(i,0,n-len+1){
can[i][len]=(str[i]==str[i+len-1] && can[i+1][len-2] );
}
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
FORE(i,0,n+1)FORE(j,1,i+1){
if(can[i-j][j])dp[i]=min(dp[i],dp[i-j]+1);
}
return dp[n];
}
};