洛谷 P3143 [USACO16OPEN] Diamond Collector S

张开发
• 2026/4/8 5:47:49 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷 P3143 [USACO16OPEN] Diamond Collector S
题目描述奶牛 Bessie 一直喜欢闪闪发光的物体她最近在业余时间开始了一项爱好——挖掘钻石她收集了 N 颗大小各不相同的钻石N≤5×104并希望将它们中的一部分放在谷仓里的两个展示柜中展示。由于 Bessie 希望每个展示柜中的钻石大小相对接近她决定如果两颗钻石的大小相差超过 K就不能将它们放在同一个展示柜中如果两颗钻石的大小相差恰好为 K则可以将它们一起展示在同一个展示柜中。给定 K请帮助 Bessie 确定她可以在两个展示柜中一起展示的最大钻石数量。输入格式输入文件的第一行包含 N 和 K0≤K≤109。接下来的 N 行每行包含一个整数表示一颗钻石的大小。所有钻石的大小均为正数且不超过 109。输出格式输出一个正整数表示 Bessie 可以在两个展示柜中一起展示的最大钻石数量。显示翻译题意翻译输入输出样例输入 #1复制7 3 10 5 1 12 9 5 14输出 #1复制5#includebits/stdc.h using namespace std; const int N410,M4e410; int f[M]; struct node{ int h,a,c; }e[N]; int n; bool cmp(node x,node y) { return x.ay.a; } int main() { cinn; for(int i1;in;i) { cine[i].he[i].ae[i].c; } sort(e1,e1n,cmp); int ret0; for(int i1;in;i) { int he[i].h,ae[i].a,ce[i].c; for(int ja;j0;j--) { for(int k0;kck*hj;k) { f[j]max(f[j],f[j-k*h]k*h); } retmax(ret,f[j]); } } coutretendl; return 0; }

更多文章