本文主要是介绍洛谷11月月赛 T2 不开心的金明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
一样大水题，不过我现在都不知道我是怎么被hack的。。
题目里有这么一句话：
要求购物单上所有的物品价格的极差（最贵的减去最便宜的）不超过3
数据范围里还有这么一句话：
min(vi)<=vi<=min(vi)+3
那么，其实只有四种价格了。。
我们称它们为0,1,2,3
然后预处理每种价格选i个的最大价值
直接暴力枚举0,1,2中选多少个，算出来3中最多选多少个，更新一下答案，就好了。。。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
struct node{ll v,p;inline bool operator < (const node& b) const {if(v==b.v)return p>b.p;return v<b.v;}
}a[101];
int n;
ll W,dp[4][101],mn=0x3f3f3f3f;
int cnt[4],sm[4];
int main(){n=read();W=read();for(int i=1;i<=n;i++)a[i].v=read(),a[i].p=read(),mn=min(mn,a[i].v);for(int i=1;i<=n;i++)cnt[a[i].v-mn]++;for(int i=1;i<4;i++)sm[i]=sm[i-1]+cnt[i-1];sort(a+1,a+n+1);for(int k=0;k<4;k++)for(int i=1;i<=cnt[k];i++)dp[k][i]=dp[k][i-1]+a[i+sm[k]].p;ll ans=0;for(int i=0;i<=cnt[0];i++){for(int j=0;j<=cnt[1];j++){for(int k=0;k<=cnt[2];k++){if(i+j+k>n)continue;ll tmp=i*mn+j*(mn+1)+k*(mn+2);tmp=W-tmp;if(tmp<0)continue;int l=tmp/(mn+3);ans=max(ans,dp[0][i]+dp[1][j]+dp[2][k]+dp[3][l]);}}}printf("%lld",ans);return 0;
}这篇关于洛谷11月月赛 T2 不开心的金明的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
