hdu2191(단조로운 대기열 최적화 dp, 다중 가방)

단조 대기열 최적화
이 dp는 이렇게 쓸 수 있다
제 i 개 아이템에 대해
dp[j+(k)*w(i)]=max(dp[j+k*w(i)]-k*w(i))+(k)*v[i].
k의 크기는 1<=k<=m[i]
갱1,push백(k)은 계산할 때 앞에 써야 돼요.
2、스크롤 그룹 사용 주의
 

#include
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int w[maxn],v[maxn],num[maxn];
int list1[maxn];
int val[maxn];
int dp[maxn],deq[maxn];
int main(){
    int i,j,k,f1,f2,f3,f4,t1,t2,t3,t4,n,m,T;
    //freopen("in.txt","r",stdin);
    //freopen("out1.txt","w",stdout);
    scanf("%d
",&T);
    while(T--){
    memset(dp,0,sizeof(dp));
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&w[i],&v[i],&num[i]);
    }
    int s,t;
    for(i=1;i<=m;i++){
        for(j=0;js&&val[k]>=val[list1[t-1]]){//t-1   ,       
                t--;
            }
            deq[t]=k; // 0  ，  s      ，  0     s    
            list1[t++]=k;
            dp[j+k*w[i]]=max(dp[j+k*w[i]],val[list1[s]]+k*v[i]);
            while(t>s&&k-deq[s]>=num[i]){ //           
            s++;
            }
        }
    }
    }
    printf("%d
",dp[n]);
    }
    return 0;
}