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; } };