SRM517 Div2 Hard(1000) CuttingGrass

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