题目描述
简述：给一些物品，两维重量，一维价值，求取一些物品满足第一种重量和不大于PP，第二种重量和不小于PP时，价值的最小值n≤1e3,P≤1e5n\le1e3,P\le1e5。
这东西我第一眼看甚至都不敢保证nPnP能不能过，~后来发现我弱到只能写nP2nP^2~。
暴力自然比较好想，就是开三维，一维下标，二维重量一，三维重量二，内容存最小价值。
咋做到nPnP呢，看到限制里面有0≤bi≤ai≤1e60\le b_i\le a_i\le 1e6，想一下，有什么用处？
既然aa的和蹭线就行bb的和不过线就行，那我们其实可以通融通融，把它们的值向中间收束，反正他俩只是状态，和答案的值没关系，过线的部分少一点不影响他已经过线的事实，没过的部分多一点也不影响他没过的状态，这样我们就可以把两个状态合并，把一个物品当成一组物品，每组物品至多取一个，物品只有一个重量，组内价值都是原来物品的价值，物品的唯一重量在组内恰好把[bi,ai][b_i,a_i]这个区间覆盖一遍，这样一来，再按类似原来的方法dpdp，只不过一维下标，二维重量，内容存价值。
这么看好像还不够，毕竟区间一大就又完蛋，但其实不是，单调队列维护区间最小值，设当前遍历到的物品是ii已达的重量是jj，那么转移就是$$f[i][j]=min(f[i-1][j],\min^{j-b[i]}_{k=j-a[i]}(f[i-1][k]+c[i]))$$
最终答案就是f[n][P]f[n][P]，因为按上面的方法拆完物品后，一定会有合法最优解卡在PP

总结：算是一种套路吧，就有一种只用满足状态的大于小于关系的可以为了优化时间来在规则允许的情况下收束来减少状态数。~（可能有什么神展开但我智力有限一时半会无法想象，等以后遇到类似的再说吧）~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define gtc() getchar()
#define fp(i,l,r) for(int i=l;i<=r;i++)
#define fb(i,l,r) for(int i=l;i>=r;i--)
#define pil pair<int,long long>
template <class T>
inline void read(T &s){
    T neg=1,ch=gtc();s=0;
    while(!isdigit(ch)){if(ch=='-')neg=-1;ch=gtc();}
    while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch-'0');ch=gtc();}
    s=s*neg;
}
const ll N=1000050;
ll t,n,m,a[N],b[N],c[N],ans=1e18,l,r,f[2][N];
struct node{
    ll v,p;
}tmp,deq[N];
int main(){
    clock_t st,ed;
    st=clock();
    freopen("shop.in","r",stdin);
    freopen("shop.out","w",stdout);
    read(n),read(m);
    fp(i,1,n)read(a[i]);
    fp(i,1,n)read(b[i]);
    fp(i,1,n)read(c[i]);
    fp(i,1,m)f[0][i]=f[1][i]=1e18;
    fp(i,1,n){
        l=r=1;
        fp(j,1,m){
            if(j-b[i]>=0){
                while(r>l&&deq[r].v>f[(i%2)^1][j-b[i]])r--;
                deq[++r].p=j-b[i],deq[r].v=f[(i%2)^1][j-b[i]];
                while(deq[l+1].p<j-a[i])l++;
                //cout<<i<<" "<<j<<" "<<deq[l+1].p<<" "<<deq[l+1].v<<endl;
                f[i%2][j]=min(f[(i%2)^1][j],deq[l+1].v+c[i]);
            }
            f[i%2][j]=min(f[i%2][j],f[(i%2)^1][j]);
        }
    }
    printf("%lld",f[n%2][m]);
    ed=clock();
    //cout<<endl<<ed-st;
    return 0;
}