SRM561Div2

Mid:
以前本番で解けなかったので復習
制約が n < 50 だったら O(n^2) か O(n^3)を
制約が n < 15 だったら O(2^n) を考えよう。(なんか方向が違う)

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

class ICPCBalloons {
public:
  int minRepaintings(vector <int> Count, string Size, vector <int> AC) {
    int res=1<<30;

    int M=0,L=0;
    vector<int> vM,vL;
    for(int i=0; i<Count.size(); ++i)
    {
      if(Size[i] == 'M')vM.push_back(Count[i]),M+=Count[i];
      if(Size[i] == 'L')vL.push_back(Count[i]),L+=Count[i];
    }
    sort(vM.rbegin(),vM.rend());
    sort(vL.rbegin(),vL.rend());

    int n = AC.size();
    for(int i=0; i<(1<<n); ++i)
    {
      int m=0,l=0;
      for(int j=0; j<n; ++j)
      {
        if(i&(1<<j))l+=AC[j];
        else m+=AC[j];
      }
      if(m>M || l>L)continue;


      vector<int> useM,useL;
      for(int j=0; j<n; ++j)
      {
        if(i&(1<<j))useL.push_back(AC[j]);
        else useM.push_back(AC[j]);
      }
      sort(useM.rbegin(),useM.rend());
      sort(useL.rbegin(),useL.rend());

      int cnt = 0;
      for(int j=0; j<useM.size(); ++j)
      {
        if(j<vM.size())cnt += max(0, useM[j] - vM[j]);
        else cnt += useM[j];
      }

      for(int j=0; j<useL.size(); ++j)
      {
        if(j<vL.size())cnt += max(0, useL[j] - vL[j]);
        else cnt += useL[j];
      }

      res = min(res, cnt);
    }

    if(res == 1<<30)return -1;
    return res;
  }
};