前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2697: 特技飞行

2697: 特技飞行

作者头像
HansBug
发布2018-04-10 16:20:49
4980
发布2018-04-10 16:20:49
举报
文章被收录于专栏:HansBug's Lab

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

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

代码语言:javascript
复制
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.         

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-12-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 2697: 特技飞行
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档