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()];
  }
};