【bzoj2697】特技飞行

我的洗发水，特级特技加特技23333 比较简单的贪心，我们可以发现只要在开头加过一遍特技就可以一直获得收益（只要在结束的时候再加一遍），所以为了获得尽可能多的收益，我们将价值大的特技尽可能放在两边，贪心的正确性其实是很显然的（废话，显不显然我都是不会证明的）

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; const int N=1010; int c[N],ans,n,k; inline int F() { register int aa,bb;register char ch; while (ch=getchar(),(ch<'0'||ch>'9'));aa=ch-'0'; while (ch=getchar(),ch<='9'&&ch>='0')aa=(aa<<3)+(aa<<1)+ch-'0';return aa; } bool cmp(const int &a,const int &b){return a>b;} int main() { cin>>n>>k; for (int i=1;i<=k;i++) c[i]=F(); sort(c+1,c+k+1,cmp); k=min(k,n/2); n--; ans=0; for (int i=1;i<=k;i++) { ans+=n*c[i]; n-=2; } cout<<ans; }