「BZOJ2697」特技飞行

2014年5月8日3,7180

Description

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

Input

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

Output

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

Sample Input

5 2
2 2

Sample Output

HINT

数据规模及约定

对于10%的测试数据，N<=20，K<=3

对于全部的测试数据，1<=N<=1000，1<=K<=300，0<=Ci<=1000。

题解

直接贪心。。价值从大到小从两边向中间放

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,ans,c[301];
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int main()
{
	n=read();k=read();
	for(int i=1;i<=k;i++)
	    c[i]=read();
	sort(c+1,c+k+1);
	int l=1,r=n;
	for(int i=k;i>0;i--)
	{
	    ans+=(r-l)*c[i];
	    l++;r--;
	    if(l>=r)break;
	}
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,k,ans,c[301];

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int main()

{

n=read();k=read();

for(int i=1;i<=k;i++)

c[i]=read();

sort(c+1,c+k+1);

int l=1,r=n;

for(int i=k;i>0;i--)

{

ans+=(r-l)*c[i];

l++;r--;

if(l>=r)break;

}

printf("%d",ans);

return 0;

}

« 「BZOJ1150」[CTSC2007] 数据备份Backup 「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会 »

hzwer.com _ Home | http://hzwer.com

「BZOJ2697」特技飞行

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论