阿祁的部落格

CSES 1159 - Book Shop II 解題心得( 題目 )

解題概念:DP、單調隊列優化

解題方法:這題是經典的多重背包問題，我們可以把物件拆開一個一個處理(假設有K個)，當成0-1背包處理，複雜度為O(NXK)，顯然不夠快。

我們可以把物件以2的次方處理，也就是拆成1、2、4、8之類的形式，讓所有數量可被組合出來，同樣當成0-1背包處理，複雜度為O(NXlogK)，還是不夠快。

因此這題使用單調隊列優化，透過越多花費結果應該要越好的特性做單調隊列，複雜度可壓到O(NX)，大概是10^7。

Java參考程式碼(更好意見可留言於下方，謝謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2021/02/04

import java.io.*;

import java.util.*;

public class cses1159 {

    public static int ret,r;

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));    

    public static int[] dp=new int[100005];

    public static int[] p=new int[100005];

    public static int[] v=new int[100005];

    public static int[] k=new int[100005];

    public static void main(String[] args) throws Exception{

        final int n=readint();

        final int x=readint();

        int cnt;

        Deque<P> dq=new LinkedList<>();

        for(int i=0;i<n;i++) {

            p[i]=readint();

        }

        for(int i=0;i<n;i++) {

            v[i]=readint();

        }

        for(int i=0;i<n;i++) {

            k[i]=readint();

        }

        for(int i=0;i<n;i++) {

            for(int j=0;j<p[i];j++) {

                dq.clear();

                cnt=0;

                for(int m=j;m<=x;m+=p[i],cnt++) {

                    while(!dq.isEmpty()&&dq.peekLast().v<dp[m]-cnt*v[i]) {

                        dq.pollLast();

                    }

                    dq.offer(new P(m,dp[m]-cnt*v[i]));

                    while(!dq.isEmpty()&&(m-dq.peekFirst().x)/p[i]>k[i]) {

                        dq.pollFirst();

                    }

                    dp[m]=dq.peekFirst().v+cnt*v[i];


                }

            }

        }

        System.out.println(dp[x]);

    }

    

    public static int readint() throws Exception {

        ret=0;

        r=br.read();

        while(r>47&&r<58) {

            ret*=10;

            ret+=(r&15);

            r=br.read();

        }

        return ret;

    }

}