3223. HEOI 2013 Ede의 새 가방 질문

제목의 대의.

아이템 n개를 주어 다중 가방으로 만듭니다.q개의 질문을 주고, 매 질문마다 아이템 하나를 제거하고, 남은 아이템에 대해 다중 가방의 답을 구합니다.
Data Constraint n≤1000,q≤3×105

문제풀이

분할을 고려하여 현재 구간 [L, R]에 대해 이 구간에 번호가 없는 물품만 만듭니다.그리고 DP를 분리하면 돼요.DP를 최적화하기 위해 단조로운 대기열을 사용해야 합니다.

단조 대기열 최적화 다중 가방

원래 DP fj=max {fj -3-kv+kw}는 분명히 모드 v의 여수에 따라 그룹을 나눌 수 있습니다.현재 j=av+b를 설정해도 무방하다. 나의 이전 결정점이 kv+b라고 가정하면
fav+b=max{fav+b−(a−k)v+(a−k)w}
fav+b=max{fb+kv−kw}+aw
그래서 단조로운 대기열로 유지보수를 해요.
fb+kv
시간 복잡도: O (nqlogn)

SRC

#include
#include
#include
#include
#include
using namespace std ;

#define N 1000 + 10
const int MAXN = 1000 ;
struct Object {
    int a , b , c ;
} P[N] ;

int Qv[N] , Qx[N] ;
int f[15][N] , ans[N][N] ;
int n , m , Cnt ;

void Calc( int l , int r ) {
    for (int i = 0 ; i <= MAXN ; i ++ ) f[Cnt][i] = f[Cnt-1][i] ;
    for (int i = l ; i <= r ; i ++ ) {
        int v = P[i].a , w = P[i].b , c = P[i].c ;
        for (int b = 0 ; b < v ; b ++ ) {
            int head = 1 , tail = 0 ;
            for (int a = 0 ; a * v + b <= MAXN ; a ++ ) {
                int last = f[Cnt][a*v+b] - a * w ;
                while ( tail >= head && Qv[tail] < last ) tail -- ;
                ++ tail ;
                Qv[tail] = last ;
                Qx[tail] = a ;
                while ( head <= tail && a - Qx[head] > c ) head ++ ;
                f[Cnt][a*v+b] = Qv[head] + a * w ;
            }
        }
    }
}

void DIV( int l , int r ) {
    if ( l == r ) {
        for (int i = 0 ; i <= MAXN ; i ++ ) ans[l][i] = f[Cnt][i] ;
        return ;
    }
    ++ Cnt ;
    int mid = (l + r) / 2 ;
    Calc( mid + 1 , r ) ;
    DIV( l , mid ) ;
    Calc( l , mid ) ;
    DIV( mid + 1 , r ) ;
    Cnt -- ;
}

int main() {
    scanf( "%d" , &n ) ;
    for (int i = 1 ; i <= n ; i ++ ) scanf( "%d%d%d" , &P[i].a , &P[i].b , &P[i].c ) ;
    DIV( 1 , n ) ;
    scanf( "%d" , &m ) ;
    for (int i = 1 ; i <= m ; i ++ ) {
        int d , e ;
        scanf( "%d%d" , &d , &e ) ;
        d ++ ;
        printf( "%d
" , ans[d][e] ) ;
    }
    return 0 ;
}

이상