1 3 5 1 5 -3 5 2 -2 2 3 2 5 3
9
不会做 参考了大佬
很显然 如果知道k那么就是一个背包问题 枚举k的话肯定是超时的
可以在坐标轴做图 x代表k 最优解是最上面那一段 很明显是一个凹函数
求凹函数的最值用到三分查找法
现在规定一下二分或者三分查找
while(l+1<r) 如果把+1去掉是不对的 可能进入死循环
然后 如果判断条件蕴含等于（可以是小于等于 或者大于等于） 将其往左靠
也就是 如果是（小于等于 或 大于等于） l=mid else r=mid
这样最后的答案肯定就是l了
还有就是注意数据范围！！！
#include<bits/stdc++.h> using namespace std; //input #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define inf 0x3f3f3f3f #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define N 500+5 int n,m,l,r; ll a[N]; ll b[N]; ll w[N]; ll v[N]; ll bag(int t) { rep(i,1,n) v[i]=a[i]*t+b[i]; ll dp[505]; CLR(dp,0); rep(i,1,n) repp(j,m,0) if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); return dp[m]; } int main() { int cas; RI(cas); while(cas--) { RIII(n,m,l);RI(r); rep(i,1,n) cin>>a[i]>>b[i]>>w[i]; while(l+1<r) { int mid=(l+r)>>1; int mmid=(mid+r)>>1; if(bag(mid)<bag(mmid)) r=mmid; else l=mid;//l包含着等于 所以答案会往l靠近 } printf("%lld\n",bag(l)); } return 0; }
原文：https://www.cnblogs.com/bxd123/p/10661178.html
