2697: 特技飞行

2697: 特技飞行

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 646  Solved: 393

[Submit][Status]

Description

神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间,每个单位时间可以进行一项特技动作,可选的动作有K种,每种动作有一个刺激程度Ci。如果连续进行相同的动作,乘客会感到厌倦,所以定义某次动作的价值为(距上次该动作的时间)*Ci,若为第一次进行该动作,价值为0。安排一种方案,使得总价值最大。

Input

  第一行,两个数,N和K,如上所述;   第二行,K个正整数,表示K种动作的Ci值。

Output

  仅一行,一个整数,表示最大总价值。

Sample Input

5 2 2 2

Sample Output

12

HINT

数据规模及约定   对于10%的测试数据,N<=20,K<=3   对于全部的测试数据,1<=N<=1000,1<=K<=300,0<=Ci<=1000。

Source

题解:这个嘛,是个萌萌哒贪心啦啦啦——先从大到小排序,然后依次往两边摆上 ,不难证明其最优性

1 var
 2    i,j,k,m,n,ll,l,r,x,y:longint;
 3    a:array[0..2000] of longint;
 4 procedure swap(var x,y:longint);inline;
 5           var z:longint;
 6           begin
 7                z:=x;x:=y;y:=z;
 8           end;
 9 procedure sort(l,r:longint);
10           var i,j,x,y:longint;
11           begin
12                i:=l;j:=r;x:=a[(l+r) div 2];
13                repeat
14                      while a[i]>x do inc(i);
15                      while a[j]<x do dec(j);
16                      if i<=j then
17                         begin
18                              swap(a[i],a[j]);
19                              inc(i);dec(j);
20                         end;
21                until i>j;
22                if i<r then sort(i,r);
23                if l<j then sort(l,j);
24           end;
25 begin
26      readln(n,m);
27      for i:=1 to m do read(a[i]);
28      readln;
29      sort(1,m);
30      x:=1;y:=n;
31      for i:=1 to m do
32          begin
33               ll:=ll+(y-x)*a[i];
34               inc(x);dec(y);
35               if x>=y then break;
36          end;
37      writeln(ll);
38      readln;

39 end.         

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1630/2023: [Usaco2005 Nov]Ant Counting 数蚂蚁

2023: [Usaco2005 Nov]Ant Counting 数蚂蚁 Time Limit: 4 Sec  Memory Limit: 64 MB Sub...

31370
来自专栏大数据文摘

奇怪的数字0.577不断出现在我们身边

15920
来自专栏C语言及其他语言

[每日一题]DNA

又到了今天C语言在线学习平台推送每日一题的时间了,今天分享的题目可能有点难,但我还是希望大家能够理解,这样以后遇到这样的问题也就不会害怕了 题目描述 小强从小...

29730
来自专栏青青天空树

生理周期(c++实现)

描述:人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23 天、 28 天和33 天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面...

10620
来自专栏企鹅号快讯

或许,这会是全民皆知的一门编程语言

不久前,国务院印发了《新一代人工智能发展规划》,其中明确指出,要实施全民智能教育项目,在中小学阶段设置人工智能相关课程,逐步推广编程教育,鼓励社会力量参与寓教于...

37850
来自专栏编程心路

从王者荣耀看设计模式-策略模式(java版)

曾经我也是一名玩农药的大学生,但现在已经弃了,别问我为什么(被坑爹队友坑的哭。。。)。而今天我们来把让农药变荣耀,我们来从王者荣耀中看设计模式的策略模式。

17450
来自专栏专知

关关的刷题日记11——Leetcode 1. Two Sum 方法2、3

关小刷刷题11 – Leetcode 1. Two Sum 方法2、3 方法2 方法2:先将数组进行排序,设置两个左右指针,若sum>target, 那么右指针...

36070
来自专栏专知

【LeetCode 344】关关的刷题日记26 Reverse String

关关的刷题日记26 – Leetcode 344. Reverse String 题目 Write a function that takes a string...

28270
来自专栏海天一树

我是如何成为一名少儿编程竞赛老师的

2017年9月,我以前一个同事问我能不能教他小孩Theo学习编程,因为以前在同一家公司时,我那同事经常带Theo去公司,我和Theo也认识,所以我答应了。

25540
来自专栏HansBug's Lab

1051: [HAOI2006]受欢迎的牛

1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 2410  Sol...

34870

扫码关注云+社区

领取腾讯云代金券