SRM555Div2
Mid:
ビット列が文字列で与えられる。
5の倍数の文字列で、与えられた文字列を分割していった時に、最小で何分割で済むか。
ただし不可能な場合は-1を返す。
ナップサックなDPをする。汚い。
#include <vector> #include <algorithm> #include <iostream> #include <string> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) class CuttingBitString { public: int getmin(string S) { vector<string> tbl; for(long long i=1; i<(1LL<<51); i*=5LL) { string s; for(int j=60; j>=0; --j) { if(s.size() && !((1LL<<j)&i))s+="0"; if((1LL<<j)&i) s+="1"; } tbl.push_back(s); } vector<int> dp(300,-1); dp[0] = 0; rep(i,S.size()){ if(dp[i]!=-1){ rep(j,tbl.size()){ if(i+tbl[j].size() > S.size())continue; bool ok=true; rep(k,tbl[j].size()){ if(S[i+k] != tbl[j][k]){ok=false;break;} } if(!ok)continue; if(S.size() == i+tbl[j].size() || ((S.size() >= i+tbl[j].size()) && (S[i+tbl[j].size()] == '1'))){ if(dp[i+tbl[j].size()] < 0)dp[i+tbl[j].size()] = dp[i] + 1; else dp[i+tbl[j].size()] = min(dp[i+tbl[j].size()], dp[i] + 1); } } } } return dp[S.size()]; } };