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