BZOJ 2697 特技飞行

题目大意

给你N个单位时间，每单位时间可以进行K个任务之一，执行一个任务获得的收益是它的权值*(这个任务上一次完成到这次完成的时间差)。求最大收益。

没想到还可以这样做= =

考虑从答案入手。答案的真实意义是第一次动作和最后一次动作的时间差*权值，所以考虑贪心解决。

向整个时间线的头尾加入权值最大的动作，时间线头尾收缩2，以此类推。

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

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

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;++i) scanf("%d",c+i);
	sort(c+1,c+k+1,greater<int>());
	for(int i=1;i<=k;++i)
	{
		if(n<2) break;
		ans+=(n-1)*c[i];
		n-=2;
	}
	printf("%d\n",ans);
	return 0;
}