題目描述

給定 nnn 對數(shù) (ai,bi)(a_i,b_i)(ai?,bi?)?和參數(shù) kkk，你需要選出一些對使得在滿足 bib_ibi? 的平均值不超過 kkk 的同時，aia_iai? 的和最大，求出這個最大值。

輸入描述:

第一行兩個整數(shù)分別表示 n,kn,kn,k。
接下來 nnn 行，每行兩個數(shù)分別表示 ai,bia_i,b_iai?,bi?

輸出描述:

一行一個整數(shù)表示答案。

示例1

輸入

復(fù)制5 6 4 10 3 4 6 7 7 7 10 8

5 6
4 10
3 4
6 7
7 7
10 8

輸出

復(fù)制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

做法

本題重點(diǎn)在這個平均數(shù)的處理。b1+b2+b3+……+bn<=n*k，也就是(b1-k)+(b2-k)+(b3-k)+……+(bn-k)<=0。那我們就先把bi全都減去k。那bi為負(fù)數(shù)的就可以全部拿下。這樣一來，我們背包的容量就是bi為負(fù)數(shù)的總和的絕對值了。

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=250010;
int n,k;
int a[N],b[N];
int dp[M];
int res,ans,sum,ans2;
struct ty{int a,b;
};
vector<ty> v;
int main(){scanf("%d%d",&n,&k);v.push_back({-1,-1});for(int i=1;i<=n;i++) {cin>>a[i]>>b[i];b[i]-=k;if(b[i]<=0) {ans+=a[i];sum+=-b[i];}else{v.push_back({a[i],b[i]});}}memset(dp,-0x3f,sizeof(dp));dp[0]=0;for(int i=1;i<v.size();i++){for(int j=sum;j>=0;j--){   if(j-v[i].b>=0)dp[j]=max(dp[j],dp[j-v[i].b]+v[i].a);}}for(int i=0;i<=sum;i++) ans2=max(dp[i],ans2);cout<<ans+ans2;
}