具体表现在,用样例测的时候,代码仿佛直接跳过了单调队列的部分。但是用普通数组构造就可以。以下是自己写的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;
}