首页 > 代码库 > BZOJ2697: 特技飞行
BZOJ2697: 特技飞行
2697: 特技飞行
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 607 Solved: 363
[Submit][Status]
Description
神犇航空开展了一项载客特技飞行业务。每次飞行长N个单位时间，每个单位时间可以进行一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。安排一种方案，使得总价值最大。
Input
第一行，两个数，N和K，如上所述；
第二行，K个正整数，表示K种动作的Ci值。
第二行，K个正整数，表示K种动作的Ci值。
Output
仅一行，一个整数，表示最大总价值。
Sample Input
5 2
2 2
2 2
Sample Output
12
HINT
数据规模及约定
对于10%的测试数据，N<=20，K<=3
对于全部的测试数据，1<=N<=1000，1<=K<=300，0<=Ci<=1000。
Source
题解：
刚开始以为是网络流？后来想了想放弃了。。。
想了想贪心，把大的放到两端？貌似正确，好像又不严密，不敢写，看看题解吧。。。
。。。。。。
感觉不会再爱了
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 500026 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 int n,m,k,a[maxn];61 inline bool cmp(int x,int y)62 {63 return x>y;64 }65 66 int main()67 68 {69 70 freopen("input.txt","r",stdin);71 72 freopen("output.txt","w",stdout);73 74 n=read();k=read();75 for1(i,k)a[i]=read();76 sort(a+1,a+k+1,cmp);77 int ans=0;78 for1(i,min(k,n/2))ans+=(n-2*i+1)*a[i];79 cout<<ans<<endl;80 81 return 0;82 83 }
BZOJ2697: 特技飞行
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。