0x01 题意

对于三个长度为 的数组 ，确定一个数组 满足 ，使得：

并最小化：

0x02 思路

对于任何一种满足条件的 数组，我们都可以通过放缩 的方式使得条件①，②均取到等号

这里考虑其中一种特殊的放缩方式，使得所有的

关于放缩

对于每一个 ，由于对 的限制条件是 ，故若 放大之后答案存在，则原答案也存在
对于每一个 ，由于对 的限制条件是 ，故若 缩小之后答案存在，则原答案也存在

因此对于每一组 ，将其拆分为 个三元组 ，每个三元组中的三个数对应原有的

这样我们就去掉了 和 的限制，转化为

将每个 拆分出的 个三元组看作一层，跑一个分组背包即可

分组背包的复杂度是 的，并不能通过此题

每一层转移时， 的转移方程是 ， 是一段连续的区间，可以用单调队列优化

时间复杂度

0x03 代码

#include <stdio.h>
#include <string.h>
#include <queue>
#define MP 10000
#define MN 1000

int n,p,a[MN+5],b[MN+5],c[MN+5],f[MP+5];

void solve(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&c[i]);
    memset(f,0x7f,sizeof(f));
    f[0] = 0;
    for(int i=1;i<=n;i++){
        std::deque<int> q;
        for(int j=p-a[i];j>=p-b[i]&&j>=0;j--){
            while(q.empty()==false&&f[j]<f[q.back()]) q.pop_back();
            q.push_back(j);
        }
        for(int j=p;j>=0;j--){
            if(!q.empty()){
                f[j] = std::min(f[j],f[q.front()]+c[i]);
                if(q.front()==j-a[i]) q.pop_front();
            }
            if(j-b[i]-1>=0){
                while(q.empty()==false&&f[j-b[i]-1]<f[q.back()]) q.pop_back();
                q.push_back(j-b[i]-1);
            }
        }
    }
    if(f[p]==0x7f7f7f7f){
        puts("IMPOSSIBLE!!!");
    }else{
        printf("%d\n",f[p]);
    }
}

int main(){
    int T; scanf("%d",&T);
    while(T--) solve();
}