YukiCoder No.54 - Happy Hallowe'en

何か解けちゃった．

解法

最大値を伝搬させていく．mx[n] := お菓子n個から最大何個とれるかとする．
最初はmx[n] = nとする．各iに対して，
mx[j] = max(mx[j], mx[j+V[i]]) (jはj < T[i]を満たすすべての非負整数)
と更新する．
iの選ぶ順序を工夫しなければならないが，T[i]+V[i]の大きい順にやればいい．
これは大きい値をもってくるものを先にやるとよさそうだということから予想できる．(適当に不等式をこねると証明できるらしい．)
計算量はO(N log N + N T_max)．N<=10^4，T_max<=10^4だが，YukiCoderは偉大なので十分に間に合う．

コード

// Wrongri-La Shower

#include <cstdio>
#include <algorithm>
#include <utility>

typedef std::pair<int,int> P;
typedef std::pair<int,P> Q;

int N;
int V[10000], T[10000];

int solve(){
    Q ps[10000];

    for(int i=0;i<N;i++){
        ps[i] = std::make_pair(T[i]+V[i], std::make_pair(T[i], V[i]));
    }
    std::sort(ps, ps+N);
    std::reverse(ps, ps+N);
    
    int mx[20001];
    for(int i=0;i<=20000;i++){
        mx[i] = i;
    }

    for(int i=0;i<N;i++){
        const P& p = ps[i].second;
        for(int j=0;j<p.first;j++){
            if(j+p.second > 20000){continue;}
            mx[j] = std::max(mx[j], mx[j+p.second]);
        }
    }
    
    return mx[0];
}

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%d %d", V+i, T+i);
    }

    printf("%d\n", solve());
}