TC SRM 517 div2 p1000 CuttingGrass

// srm517div2p1000.cpp
//
// 1. each pos is cut <= 1 times
// if not, then can postpone the first cut to merge with the second cut, this
// results in a better configuration
//
// 2. once a subset of pos are cut, then the best way is to order cuts by
// increasing grow[pos]
//
// The DP solution is to calc(int day, int pos, int T), the total height
// for grass[pos..N-1] after we decide cuts up to day.
// and we try all T=1,...,N
//
// another solution is to use max-weight-matching, due to idy
// L is grass set, R is day set
// w[l][r] = height that got cut if we cut grass[l] at day[r]
// try all T=1,...,N
// find a max-weight-matching of size T, then the total height is
// sum init[i]+grow[i]*T - matching
//
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

struct Grass
{
    int grow, init;
};

bool operator<(const Grass &g1, const Grass &g2)
{
    return g1.grow < g2.grow;
}

int N;
vector<Grass> G;
int dp[51][51]; // day,pos

class CuttingGrass
{
public:
int theMin(vector<int> init, vector<int> grow, int H);
};

int calc(int day, int pos, int T)
{
    if (pos>=N) return 0;
    int &ans=dp[day][pos];
    if (ans>=0) return ans;
    ans = G[pos].init+G[pos].grow*T + calc(day,pos+1,T);// no cut on pos
    if (day<T) {
        int tmp = G[pos].grow*(T-day-1) + calc(day+1,pos+1,T); // cut on pos
        ans=min(ans,tmp);
    }
    return ans;
}

int CuttingGrass::theMin(vector<int> init, vector<int> grow, int H)
{
    N=int(init.size());
    int sum=0;
    for(int i=0; i<N; ++i) sum+=init[i];
    if (sum<=H) return 0;
    G.resize(N);
    for(int i=0; i<N; ++i) { Grass g={grow[i],init[i]}; G[i]=g; }
    sort(G.begin(), G.end());
    for(int t=1; t<=N; ++t)
    {
        memset(dp,-1,sizeof dp);
        if (calc(0,0,t)<=H) return t;
    }
    return -1;
}