P1853 投资的最大效益

Koei · 2025-10-03 20:22:51 · 算法·理论

本题为完全背包的模板题，只是如果要过hack需要一些特殊处理

一种错误情况：在基本的完全背包外加一个循环for_{1\sim n}使其符合题意

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e6+10);
int s,n,d;
int w[maxn],v[maxn],dp[maxn];
int main(){
    cin>>s>>n>>d;
    for(int i(1);i<=d;i++){
        cin>>w[i]>>v[i];
    }
    for(int i(1);i<=n;i++){
        for(int j(1);j<=d;j++){
            for(int k(w[j]);k<=s;k++){
                if(k>=(w[j])){
                    dp[k]=max(dp[k],dp[k-(w[j])]+v[j]);
                }
            }
        }
        s+=dp[m];
        memset(dp,0,sizeof(dp));
    }
    cout<<s<<'\n';
}

提交后发现hack过不去TLE了

经过观察可以发现a是1000的倍数 也就是说a\ge 1000所以dp_{1\sim1000}几乎没有意义，那么如果将这一段没用的区间省略掉，这样就可以使memset的复杂度降低

既然a是1000的倍数那么在计算dp时除1000，就可以省略掉多余空间降低时间

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e6+10);
int s,n,d;
int w[maxn],v[maxn],dp[maxn];
int main(){
    cin>>s>>n>>d;
    for(int i(1);i<=d;i++){
        cin>>w[i]>>v[i];
    }
    for(int i(1);i<=n;i++){
        int m(s/1000);
        for(int j(1);j<=d;j++){
            for(int k(w[j]/1000);k<=m;k++){
                if(k>=(w[j]/1000)){
                    dp[k]=max(dp[k],dp[k-(w[j]/1000)]+v[j]);
                }
            }
        }
        s+=dp[m];
        memset(dp,0,sizeof(dp));
    }
    cout<<s<<'\n';
}