问题：
Problem Statement 有 N 块羊肉穿在同一根竹签上，从左到右美味值 依次为 V1, V2, ..., VN。注意美味值可能为负数。 现在你想把一些羊肉夹到自己的盘子里。 你至多可以进行 K 次操作，可选择的操作如下： 操作 A：将羊肉串上最左端的羊肉夹到盘子中，必须保证羊肉串上有羊肉 操作 B：将羊肉串上最右端的羊肉夹到盘子中，必须保证羊肉串上有羊肉 操作 C：将盘子中的某块羊肉重新穿到羊肉串的最左端，必须保证盘子中有羊肉 操作 D：将盘子中的某块羊肉重新穿到羊肉串的最右端，必须保证盘子中有羊肉 找出夹到盘子中的羊肉的美味值之和的最大可能。 Constraints 所有输入的值都是整数 1 ≤ N ≤ 50 1 ≤ K ≤ 100 -107 ≤ Vi ≤ 107 Input 输入按以下格式由 标准输入 给出： N K V1 V2 ... VN Output 输出夹到盘子中的羊肉的美味值之和的最大可能。 Sample Input 1 6 4 -10 8 2 1 2 6 Sample Output 1 14 通过以下操作，你将会得到两块美味值分别为 8 和 6 的羊肉，总和 14 为最大值。 操作 A，把美味值为 -10 的羊肉夹到盘中 操作 B，把美味值为 6 的羊肉夹到盘中 操作 A，把美味值为 8 的羊肉夹到盘中 操作 D，把美味值为 -10 的羊肉穿回羊肉串的右端 Sample Input 2 6 4 -6 -100 50 -2 -5 -3 Sample Output 2 44 Sample Input 3 6 3 -6 -100 50 -2 -5 -3 Sample Output 3 0 什么都不做才是最优的。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue
#include <map>
#include <set> //multiset set<int,greater<int>> //big->small
#include <vector> // vector<int>().swap(v);清空释放内存
#include <stack>
#include <cmath> // auto &Name : STLName Name.
#include <utility>
#include <sstream>
#include <string> //__builtin_popcount(ans);//获取某个数二进制位1的个数
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAX_N = 1000 +10;
const int MOD = 1000000007;
const int SZ = 1<<20; //fast io
struct fastio{
char inbuf[SZ];
char outbuf[SZ];
fastio(){
setvbuf(stdin,inbuf,_IOFBF,SZ);
setvbuf(stdout,outbuf,_IOFBF,SZ);
}
}io;
int read()
{
int x=0,f=1;char ch=getchar();
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 n,m,a[MAX_N],b[MAX_N],ans=0;
int main(void)
{
// ios::sync_with_stdio(false);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int k=min(m,n);
for(int l=0;l<=k;l++)
{
for(int r=0;r<=k;r++)
{
for(int i=0;i<l;i++) b[i]=a[i];
for(int j=0;j<r;j++) b[l+j]=a[n-j-1];
sort(b,b+l+r);
int k=0,temp=0;
while(k+l+r<m && b[k]<0)
k++;
while(k < l+r)
{
temp+=b[k];
k++;
}
ans=max(ans,temp);
}
}
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/jaszzz/p/12891182.html