单调队列优化DP

FJ_00460 · 2025-02-10 20:22:36 · 个人记录

算法步骤：

• 第一个元素进队，队头队尾指针指向第一个元素
• 对于其他的N-1个未入队的元素，执行以下操作

  
  for(int i = 1 ; i <= n ; i ++){
  cin >> c[i] >> w[i] >> num[i];//c, w, num分别对应 体积 价值 个数
  if(V / c[i] < num[i])
      num[i] = V / c[i];//求lim
  for(int mo = 0; mo < c[i]; mo ++){//枚举余数 
      head = tail = 0;//队列初始化 
      for(int k = 0; k <= (V - mo) / c[i]; k++){
          int x = k;
          int y = dp[k * c[i] + mo] - k * w[i];
          while(head < tail && que[head].pos < k - num)head++;//限长度
          while(head < tail && que[tail - 1].value <= y)tail --;
          que[tail].value = y;
          que[tail].pos = x;
          tail ++;
          dp[k * c[i] + mo] = que[head].value + k * w[i];
          //加上k * w[i]的原因：单调队列维护的是前i - 1中的状态最大值 
          //因此这里加上 
      }
  } 

}```