SRM517 Div2 Hard(1000) CuttingGrass
同じ葉を2回切る意味は無い。切る葉を決めれば、growの小さいものから順に切っていくのが最善。葉をglowの値でソートしてから、動的計画法で、i番目までの葉の中からj本を切った時の最小合計長を求めていく。glowの値でソートしたことで、最後に切るのはそのとき計算している葉となる。最小合計長がHを超えない最小の本数が答え。
#include <vector> #include <algorithm> #include <utility> #include <numeric> using namespace std; template <class S,class T> void pairsort(vector<S>*a,vector<T>*b){ int n=(int)a->size(); vector<pair<S,T> >t(n);for(int i=0;i<n;i++)t[i]=make_pair((*a)[i],(*b)[i]); sort(t.begin(),t.end()); for(int i=0;i<n;i++)(*a)[i]=t[i].first,(*b)[i]=t[i].second; } class CuttingGrass{public: int theMin( vector <int> init, vector <int> grow, int H ) { int n = (int)init.size(); pairsort( &grow, &init ); // T[i][j]: i番目までの葉の中でj本を切った時の最小合計長 vector<vector<int> > T( n, vector<int>(n+1) ); T[0][0] = init[0]; T[0][1] = 0; for ( int i=1; i<n; i++ ) { int g = accumulate(grow.begin(),grow.begin()+i,0); T[i][0] = T[i-1][0]+init[i]; for ( int j=1; j<=i; j++ ) T[i][j] = min( T[i-1][j]+init[i]+grow[i]*j, T[i-1][j-1]+g ); T[i][i+1] = T[i-1][i]+g; } for ( int i=0; i<=n; i++ ) if ( T[n-1][i]<=H ) return i; return -1; }};