为何单调队列用stl的deque会完全没有用
  • 板块P1833 樱花
  • 楼主littlecyber
  • 当前回复0
  • 已保存回复0
  • 发布时间2020/7/28 00:15
  • 上次更新2023/11/6 22:02:52
查看原帖
为何单调队列用stl的deque会完全没有用
323744
littlecyber楼主2020/7/28 00:15

具体表现在,用样例测的时候,代码仿佛直接跳过了单调队列的部分。但是用普通数组构造就可以。以下是自己写的deque的版本:

#include <bits/stdc++.h>
#define memset(a,b) memset(a,b,sizeof(a))
#define maxn 1000+10
#define maxm 10000+10
//多重背包的一般解法,也就是在01背包框架上多几次物品个数的循环
using namespace std;
int w[maxm],c[maxm],num[maxm],dp[maxn],q[maxm],pos[maxm];
struct node{
    int ind,v;
};
int main()
{
    int t=0,n;
    string T[2];
    cin>>T[0]>>T[1]>>n;memset(dp,0);
    for(int i=0;i<2;i++){
        int tp=T[i].find(":");
        t+=(i*2-1)*(60*((tp==1)?(T[i][tp-1]-'0'):((T[i][tp-2]-'0')*10+T[i][tp-1]-'0'))+10*(T[i][tp+1]-'0')+T[i][tp+2]-'0');
    }
    for(int i=0;i<n;i++){
        cin>>w[i]>>c[i]>>num[i];
        if(num[i]==1)for(int j=t;j>=w[i];j--)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        else if(num[i]==0)for(int j=w[i];j<=t;j++)dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
        else{
            deque<node> que;
            for(int m=0;m<w[i];m++){
                for(int k=0;k<=(t-m)/w[i];k++){
                    int r=k*w[i]+m;
                    while(!que.empty()&&que.front().ind<k-min(p[i],t/w[i]))que.pop_front();
                    node tp={k,dp[r]-k*c[i]};que.push_back(tp);
                    while(!que.empty()&&que.back().v<=dp[r]-k*c[i])que.pop_back();
                    dp[r]=que.front().v+k*c[i];cout<<r<<endl;
                }
            }
        }
    }
    cout<<dp[t];
    return 0;
}

2020/7/28 00:15
加载中...