【BZOJ】2697: 特技飞行
BZOJ
2023-09-27 14:22:21 时间
题意
\(k(1 \le k \le 300)\)种物品,价值分别为\(c_i(0 \le c_i \le 1000)\)。有\(n(1 \le n \le 1000)\)分钟,每分钟可以选择一个物品\(i\),价值为距离上次选择该物品的时间 * \(c_i\)。求最大价值。
分析
发现对于一种物品,价值为\(c_i * \sum_{j=2}^{a} (t_j-t_{j-1}) = c_i * (t_a-t_1)\)。\(t_i\)表示第\(i\)次选这个物品的时间。这样,我们只需要为每一个物品找到一个开始和结束时间的时间即可。
由于考虑任意两种物品及其位置对其它的物品的贡献无影响,所以我们考虑任意两种物品。
对于两种物品\(i, j\),假设\(c_i \ge c_j\),他们开始和结束时间分别为\(l_i, r_i\)和\(l_j, r_j\),则最优解中肯定\(l_i < l_j, r_j < r_i\),证明如下:
首先显然肯定不可能\(l_j < l_i, r_i < r_j\)。
假设\(l_i < l_j, r_i < r_j\)(\(l_j < l_i, r_j < r_i\)证明类似),则可以证明将\(r_i, r_j\)交换后更优(证明大简单,略)。
所以我们将物品排序后,一个个取即可。
题解
所以贪心地取即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
int n, k, a[N];
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=k; ++i) {
scanf("%d", &a[i]);
}
sort(a+1, a+1+k);
int num=n-1;
ll ans=0;
for(int i=k; i; --i) {
if(num<0) {
break;
}
ans+=(ll)num*a[i];
num-=2;
}
printf("%lld\n", ans);
return 0;
}
相关文章
- bzoj-2243 染色
- BZOJ 3531 SDOI2014 旅行 树链剖分
- BZOJ 2006 NOI2010 超级钢琴 划分树+堆
- bzoj 1218 [HNOI2003]激光炸弹
- BZOJ 3514 Codechef MARCH14 GERALD07加强版 Link-Cut-Tree+划分树
- BZOJ 2440 [中山市选2011]完全平方数 (二分 + 莫比乌斯函数)
- BZOJ 2005 [Noi2010]能量采集 (数学+容斥 或 莫比乌斯反演)
- BZOJ 2120 数颜色 (带修莫队)
- BZOJ 1007 [HNOI2008]水平可见直线 (栈)
- BZOJ 1935 Tree 园丁的烦恼 (树状数组)
- 【BZOJ 1701】Cow School(斜率优化/动态凸包/分治优化)
- BZOJ 1055 HAOI2008 玩具取名 动态规划
- BZOJ 1007 HNOI2008 水平可见直线 半平面交
- BZOJ 1005 明明的烦恼 Prufer序列+组合数学+高精度