naoya_t@topcoder

SRM394 Div1 Easy: RoughStrings

過去問, 練習 | 05:57 |

TLE

・・・メモ化しないと駄目です

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class RoughStrings {
  int n_;
  map<vector<int>,int> memo;

  int sub(vector<int> v, int d){
    remove_(v,0); // メモ参照の前に0要素を消さないと激しく遅い
    if(found(memo,v)) return memo[v]; // これが後
    int l=v.size(); if(l<=1) return 0;
    sort(all(v));
    int minr = v[l-1]-v[0];
    if(d==n_) return memo[v]=minr;

    if (v[0]>0) {
      v[0]--;
      minr = min(minr,sub(v,d+1));
      v[0]++;
    }
    v[l-1]--;
    minr = min(minr,sub(v,d+1));
    v[l-1]++;
    return memo[v]=minr;
  }
public:
  int minRoughness(string s, int n) {
    n_=n;
    vector<int>cn(26,0);
    int m=s.length(); //1-50
    rep(i,m) cn[s[i]-'a']++;
    return sub(cn,0);
  }
};