单调队列优化dp20pts求调，玄关

崛起的滑稽 @ 2024-07-10 16:39:53

#include <bits/stdc++.h>
#define int __int128
using namespace std;
namespace LYH{
    template<typename T>inline void input(T &x){
        char c='?';
        bool flag=false;//正负
        x=0;
        while(c=getchar(),!isdigit(c)){
            if(c=='-'){
                flag=true;
            }
        }
        while(isdigit(c)){
            x=x*10+(c-'0');
            c=getchar();
        }
        if(flag){
            x=-x;
        }
    }
    template<typename T>inline void print(T x){
        if(x<0){
            x=-x;
            putchar('-');
        }
        if(x>9){
            print(x/10);
        }
        putchar(char(x%10+'0'));
    }
    class double_queue
    {
    public:
        void pop_front()
        {
            if(head<=tail)
                ++head;
        }
        void pop_back()
        {
            if (head <= tail)
            {
                q.pop_back();
                --tail;
            }
        }
        void push_back(int value)
        {
            q.push_back(value);
            ++tail;
        }
        void push_front(int value){
            if(head){
                ++tail;
                q.insert(q.begin(),value);
                return;
            }
            q[--tail]=value;
        }
        void clear()
        {
            q.clear();
            head=0;
            tail=-1;
        }
        bool empty(){return !(head<=tail);}
        int front() { return q[head]; }
        int back() { return q[tail]; }
        int begin() { return head; }
        int end() { return tail; }
        std::vector<int>::iterator beginP() { return q.begin(); }
        std::vector<int>::iterator endP(){ return q.end(); }
    private:
        std::vector<int> q;
        int head = 0, tail = -1;

    };
}
//______________________________分割线____________________________以下为有效代码
const int MAXN=1e6+10;
int n,k,a,dp[MAXN],s[MAXN],ds[MAXN];
LYH::double_queue q;
signed main(){
    LYH::input(n);
    LYH::input(k);
    q.push_back(0);
    for(int i=1;i<=n;++i){
        LYH::input(a);
        s[i]=s[i-1]+a;
        ds[i]=dp[i-1]-s[i];
        while(!q.empty()&&q.front()<i-k){
            q.pop_front();
        }
        while(!q.empty()&&dp[q.back()]<ds[i]){
            q.pop_back();
        }
        q.push_back(i);
        dp[i]=ds[q.front()]+s[i];
    }
    LYH::print(dp[n]);
}

by D0000 @ 2024-07-18 20:49:09

问题有点多，但都是小问题。

首先你只用了 dp[i] 表示前 i 个数的答案，其实上应该分 dp[i] 和 dp2[i] 分别表示第 i 个数选或不选的答案。而上面的代码中大部分混用了这 2 种。见修改后的代码：

#include <bits/stdc++.h>
#define int __int128
using namespace std;
namespace LYH{
    template<typename T>inline void input(T &x){
        char c='?';
        bool flag=false;//正负
        x=0;
        while(c=getchar(),!isdigit(c)){
            if(c=='-'){
                flag=true;
            }
        }
        while(isdigit(c)){
            x=x*10+(c-'0');
            c=getchar();
        }
        if(flag){
            x=-x;
        }
    }
    template<typename T>inline void print(T x){
        if(x<0){
            x=-x;
            putchar('-');
        }
        if(x>9){
            print(x/10);
        }
        putchar(char(x%10+'0'));
    }
    class double_queue
    {
    public:
        void pop_front()
        {
            if(head<=tail)
                ++head;
        }
        void pop_back()
        {
            if (head <= tail)
            {
                q.pop_back();
                --tail;
            }
        }
        void push_back(int value)
        {
            q.push_back(value);
            ++tail;
        }
        void push_front(int value){
            if(head){
                ++tail;
                q.insert(q.begin(),value);
                return;
            }
            q[--tail]=value;
        }
        void clear()
        {
            q.clear();
            head=0;
            tail=-1;
        }
        bool empty(){return !(head<=tail);}
        int front() { return q[head]; }
        int back() { return q[tail]; }
        int begin() { return head; }
        int end() { return tail; }
        std::vector<int>::iterator beginP() { return q.begin(); }
        std::vector<int>::iterator endP(){ return q.end(); }
    private:
        std::vector<int> q;
        int head = 0, tail = -1;

    };
}
//______________________________分割线____________________________以下为有效代码
const int MAXN=1e6+10;
int n,k,a,dp[MAXN],s[MAXN],ds[MAXN],dp2[MAXN];
LYH::double_queue q;
signed main(){
    LYH::input(n);
    LYH::input(k);
    q.push_back(0);
    for(int i=1;i<=n;++i){
        LYH::input(a);
        s[i]=s[i-1]+a;
        dp[i]=max(dp[i-1],dp2[i-1]);// 先算不选第 i 个数 
        ds[i]=dp[i]-s[i]; // 原始代码写的是 dp[i-1] 显然不对 
        while(!q.empty()&&q.front()<i-k){
            q.pop_front();
        }
        dp2[i]=ds[q.front()]+s[i];// 这是选 i 个数 
        while(!q.empty()&&ds[q.back()]<ds[i]){//原始代码写的是 ds[q.back()]<dp[i] 显然不对 
            q.pop_back();
        }
        q.push_back(i);

    }
    LYH::print(max(dp[n],dp2[n]));// 选不选最后一个数都行 
}

by D0000 @ 2024-07-18 20:59:37

当然也有可能你的解法和我不一样，是别的问题。

by 崛起的滑稽 @ 2024-10-13 18:50:57

@D0000 谢谢dalao（抱歉不知道为啥没看见虽然太晚了但是该谢还得谢（））