問題
http://community.topcoder.com/stat?c=problem_statement&pm=12155&rd=15177
解き方
ｄｐで解く。ｎは５０なので整数の最大は2^50=10^15程度なのでlong longで
表すことができる。
コード
class CuttingBitString {
public:
bool ispossible(string s){
if(s[0]=='0')return false;
int n=s.size();
long long ret=0,p=1;
for(int i=n-1;i>=0;i--){
ret+=(s[i]-'0')*p;
p*=2;
}
if(ret==0)return false;
while(ret%5==0 && ret>0)ret/=5;
return ret==1;
}
int getmin(string S) {
int n=S.size();
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++)if(dp[j]!=1e+9){
if(ispossible(S.substr(j,i-j+1))){
dp[i+1]=min(dp[i+1],dp[j]+1);
}
}
}
return dp[n]==1e+9 ? -1 : dp[n];
}
};
public:
bool ispossible(string s){
if(s[0]=='0')return false;
int n=s.size();
long long ret=0,p=1;
for(int i=n-1;i>=0;i--){
ret+=(s[i]-'0')*p;
p*=2;
}
if(ret==0)return false;
while(ret%5==0 && ret>0)ret/=5;
return ret==1;
}
int getmin(string S) {
int n=S.size();
int dp[n+1];
FORE(i,0,n+1)dp[i]=1e+9;
dp[0]=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++)if(dp[j]!=1e+9){
if(ispossible(S.substr(j,i-j+1))){
dp[i+1]=min(dp[i+1],dp[j]+1);
}
}
}
return dp[n]==1e+9 ? -1 : dp[n];
}
};