0w1

JOI 11 本選 Night Market ( 区間DP )

Night Market | Aizu Online Judge
ナップサック問題に変換するまでは簡単に見破れるが、問題はどう実装するかだ。愚直に解こうとするとO( n ^ 2 * t )になってしまうので、セグメント木を使いました。実は左からと右からとそれぞれ1回ずつナップサックをすればO( n * t )でできる様で、僕はもうセグメント木に頼りすぎていると思うが、ACしたからそれが楽ならそれでよしと。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3000 + 3;
const int MAXT = 3000 + 3;
const int MAXA = 1e5 + 5;
const int MAXB = 3000 + 3;

struct itvt{
    int maxv;
    int lb, rb;
    itvt *lc, *rc;
    itvt(): maxv(0), lc(NULL), rc(NULL){}
    void pull(){
        maxv = max<int>( lc->maxv, rc->maxv );
    }
};

itvt* buildItvt(int lb, int rb){
    itvt *t = new itvt();
    t->lb = lb, t->rb = rb;
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    return t;
}

void update(itvt *t, int k, int v){
    if( t->lb == t->rb ){
        t->maxv = max<int>( t->maxv, v );
        return;
    }
    int mid = t->lb + t->rb >> 1;
    if( k <= mid ) update( t->lc, k, v );
    else update( t->rc, k, v );
    t->pull();
}

int qmax(itvt *t, int ql, int qr){
    if( qr < t->lb || t->rb < ql ) return 0;
    if( ql <= t->lb && t->rb <= qr ) return t->maxv;
    int mid = t->lb + t->rb >> 1;
    int res = 0;
    if( ql <= mid ) res = max( res, qmax( t->lc, ql, qr ) );
    if( mid <  qr ) res = max( res, qmax( t->rc, ql, qr ) );
    return res;
}

int n, t, s;
int a[ MAXN ], b[ MAXN ];

int dp[ MAXT ]; // maximum joy on time i, ( i is free )

void solve(){
    itvt *root = buildItvt( 0, t );
    for(int i = 0; i < n; ++i)
        for(int j = t - b[ i ]; j >= 0; --j){
            if( j < s && s < j + b[ i ] ) continue;
            if( j + b[ i ] <= s ){
                dp[ j + b[ i ] ] = qmax( root, 0, j ) + a[ i ];
                update( root, j + b[ i ], dp[ j + b[ i ] ] );
            } else{
                dp[ j + b[ i ] ] = qmax( root, s, j ) + a[ i ];
                update( root, j + b[ i ], dp[ j + b[ i ] ] );
            }
        }
    printf("%d\n", qmax( root, 0, t ));
}

int main(){
    scanf("%d%d%d", &n, &t, &s);
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[ i ], &b[ i ]);
    solve();
    return 0;
}