https://www.luogu.com.cn/problem/P1833
思路：首先比较容易想到是取和不取的背包问题，其次发现里面有完全背包和多重背包。所以朴素的做法就是当前物品是多重背包时候，用多重背包的解法，当前背包是完全背包时候，用完全背包的解法。
这样会T两个点。当然你开O2可以过，但是没必要。
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e5+100; typedef long long LL; LL dp[maxn],t[maxn],c[maxn],p[maxn]; int main(void) { ///cin.tie(0);std::ios::sync_with_stdio(false); LL a1,a2,a3,a4; scanf("%lld:%lld",&a1,&a2); scanf("%lld:%lld",&a3,&a4); LL n;scanf("%lld",&n); LL times1=0; LL times2=0; times1=a1*3600+a2*60; times2=a3*3600+a4*60; LL T=(times2-times1)/60; for(LL i=1;i<=n;i++){ scanf("%lld%lld%lld",&t[i],&c[i],&p[i]); } memset(dp,0,sizeof(dp)); for(LL i=1;i<=n;i++) { if(p[i]==0){ for(LL j=t[i];j<=T;j++) { dp[j]=max(dp[j],dp[j-t[i]]+c[i]); } } else { for(LL k=1;k<=p[i];k++) { for(LL j=T;j>=t[i];j--) { dp[j]=max(dp[j],dp[j-t[i]]+c[i]); } } } } printf("%lld\n",dp[T]); return 0; }
考虑优化：在做多重背包的部分，是朴素的把其物品拆成一个一个的，考虑每个取还是不取，成为了一个01背包问题，转化成枚举取几个。
那么这里是可以用类似倍增的思想二进制优化的。
记录当前物品的总个数(假设有n个）和总价值，按照二进制将其log(n)堆,同时每一堆的价值是该堆的数量×该物品的单价。
比如8件单价为4的物品A，分成(1,4),(2,8)(4,16)(5,20)最多了。当然这里最后的那部分不够20就直接把最后一部分凑成一堆。
这样选几个的问题转化到了选几堆的问题，比如选1和3堆，就相当于选了5个，总和为20的物品，对应原来01中朴素的一个个选的时候枚举到5个的时候。
代码上注意：空间给够。因为要考虑每个物品多出来的数量。
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=999999; typedef long long LL; LL dp[maxn],t[10010],c[10010],p[10010],col[maxn],val[maxn]; LL cnt=0,n; void pre() { for(LL i=1;i<=n;i++){ LL tot=1; while(p[i]>0) { col[++cnt]=tot*t[i]; val[cnt]=tot*c[i]; p[i]-=tot;tot*=2; if(p[i]<tot&&p[i])///2020.10.21.update:&&p[i](虽然这里没事，但是判定性问题的时候会多出一个cnt { col[++cnt]=p[i]*t[i]; val[cnt]=c[i]*p[i]; break; } } } } int main(void) { LL s1,s2,s3,s4; scanf("%lld:%lld",&s1,&s2); scanf("%lld:%lld",&s3,&s4); LL times1=s1*3600+s2*60; LL times2=s3*3600+s4*60; LL T=(times2-times1)/60; scanf("%lld",&n); for(LL i=1;i<=n;i++){ scanf("%lld%lld%lld",&t[i],&c[i],&p[i]); if(p[i]==0) p[i]=999999; } pre(); for(LL i=1;i<=cnt;i++) { for(LL j=T;j>=col[i];j--) { dp[j]=max(dp[j],dp[j-col[i]]+val[i]); } } cout<<dp[T]<<endl; }
