luogu p3918[国家集训队]特技飞行 贪心

集训队]特技飞行 贪心"/>

luogu p3918[国家集训队]特技飞行 贪心

开始没看出来是贪心，一度以为是动态规划，还是太弱了呀…..
不难分析出，两个相同的飞行动作之间夹一个相同的动作是多余的，所以就贪心一下，按Ci从大到小排序，依次加到左右两端点，知道加不了为止。
代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 305;
int val[maxn];
int cmp(int i,int j)
{return i >j;
}
int main()
{long long ans = 0;int n,k;scanf("%d%d",&n,&k);for(int i = 1;i <= k;++i)scanf("%d",&val[i]);sort(val+1,val+1+k,cmp);int l = 1, r = n;for(int i = 1;i <= k;++i){ans += (r-l)*val[i];++l, --r;if(l>=r)break;}printf("%lld",ans);return 0;
}