保山 网站建设,网页播放视频 网站开发,wordpress 域名分离,公司名称大全简单大气三个字题目描述
给定 nnn 对数 (ai,bi)(a_i,b_i)(ai,bi) 和参数 kkk#xff0c;你需要选出一些对使得在满足 bib_ibi 的平均值不超过 kkk 的同时#xff0c;aia_iai 的和最大#xff0c;求出这个最大值。
输入描述:
第一行两个整数分别表示 n,kn,kn,k。
接下来 nnn 行你需要选出一些对使得在满足 bib_ibi 的平均值不超过 kkk 的同时aia_iai 的和最大求出这个最大值。
输入描述:
第一行两个整数分别表示 n,kn,kn,k。
接下来 nnn 行每行两个数分别表示 ai,bia_i,b_iai,bi输出描述:
一行一个整数表示答案。
示例1
输入
复制5 6 4 10 3 4 6 7 7 7 10 8
5 6
4 10
3 4
6 7
7 7
10 8
输出
复制16
16
备注:
0≤ai,bi,k≤500,1≤n≤5000 \le a_i,b_i,k \le 500,1 \le n \le 5000≤ai,bi,k≤500,1≤n≤500
做法
本题重点在这个平均数的处理。b1b2b3……bnn*k也就是(b1-k)(b2-k)(b3-k)……(bn-k)0。那我们就先把bi全都减去k。那bi为负数的就可以全部拿下。这样一来我们背包的容量就是bi为负数的总和的绝对值了。
#includebits/stdc.h
using namespace std;
const int N510,M250010;
int n,k;
int a[N],b[N];
int dp[M];
int res,ans,sum,ans2;
struct ty{int a,b;
};
vectorty v;
int main(){scanf(%d%d,n,k);v.push_back({-1,-1});for(int i1;in;i) {cina[i]b[i];b[i]-k;if(b[i]0) {ansa[i];sum-b[i];}else{v.push_back({a[i],b[i]});}}memset(dp,-0x3f,sizeof(dp));dp[0]0;for(int i1;iv.size();i){for(int jsum;j0;j--){ if(j-v[i].b0)dp[j]max(dp[j],dp[j-v[i].b]v[i].a);}}for(int i0;isum;i) ans2max(dp[i],ans2);coutansans2;
}
