别走！
我用的是单调队列优化的多重背包做法。
然后由于只需要上一层dp和记录当前层dp，我只开了dp[2][N]结果WA，我寻思没错啊。然后我开了dp[3][N]就AC了，这不是神经病吗？？？
下面是我的代码：

//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>  

using namespace std;
    
#define ll long long
#define for1(i,a,b) for (int i=(a);i<=(b);i++)
#define for0(i,a,b) for (int i=(a);i<(b);i++)
#define rof1(i,a,b) for (int i=(a);i>=(b);i--)
#define rof0(i,a,b) for (int i=(a);i>(b);i--)
#define pb push_back
#define fi first
#define se second
#define duozu int __T;scanf("%d",&__T);for1(ica,1,__T)
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%I64d", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
void W(){}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
void _R(const int& x){ scanf("%d", &x); }
void _R(const ll& x){ scanf("%I64d", &x); }
void _R(const char* x){ scanf("%s", x); }
void R(){}
template<class T,class... U> void R(const T& head,const U& ...tail){_R(head);R(tail...);}
const ll mod = 1e9+7;
ll ft1(ll a,ll b){ll ans = 1;while (b){if (b&1) ans *= a;b>>=1,a*=a;}return ans;}
ll ft2(ll a,ll b){ll ans = 1;while (b){if (b&1) ans = ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
    
const int N = 1e5+5;
    
int l[N],r[N];

int dp[2][N];
int v[N],w[N],n[N];

struct P{
    int fi,se;
}sta[N];

int main()
{
    int V,m;

    while (~scanf("%d %d",&V,&m)){

        memset(dp[0],0,sizeof(int)*(V+1));
        memset(dp[1],0,sizeof(int)*(V+1));

        for1(i,1,m) R(n[i],w[i]),v[i] = w[i];
        
        int cur = 0,now = 1;

        for1(i,1,m){//前i件
            for0(d,0,v[i]){//余数为d
 
                int st=1,ed=0;
                for (int x=0;x*v[i]<=V;x++){//求dp[i][d+x*v] = sta[max(x-n[i]+1,0)~x] + x*w[i]
                    int ww = dp[cur][d+x*v[i]] - x*w[i];
                    while (st<=ed && ww>sta[ed].se) ed--;
                    sta[++ed] = {x,ww};
                    int border = max(x-n[i],0);
                    while (st<=ed && sta[st].fi<border) st++;
                    dp[now][d+x*v[i]] = sta[st].se + x*w[i];
                }
            }
            swap(cur,now);
        }
        W(dp[cur][V]);

    }
    return 0;
}

• Re:震惊！ (2552) 1843172768 2020-01-12 19:48:31
• Re:震惊！ (69) 1843172768 2020-01-12 19:50:37