2023-01-14

题目传送门

翻译

难度&重要性(1~10):

题目来源

AtCoder

题目算法

暴力，贪心

解题思路

由题意可以得出，数据只有 \(n \leq 50,k \leq 100\)。所以，可以使用暴力，枚举从左右两边取的个数（只能从两边取），用一个数组记录下负数，去玩两边之后，将负数排个序，再用剩下的步骤，每次将最小的负数放回原序列（正数不要丢！），直到步骤用完或者负数全部放回原序列。最后找出最大值即可。

完成状态

已完成

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[1000005];
int fs[10005],tot;//fs记录负数
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n-i;j++){//不能将全部取完
			if(i+j>m) continue;//不能超过步数
			int sum=0;//sum记录当前方案的值
			tot=0;
			for(int k=1;k<=i;k++){
				sum+=a[k];
				if(a[k]<0)
					fs[++tot]=a[k];//从左边取出i个数，并将负数加入到fs数组中
			}
			for(int k=n;k>=n-j+1;k--){
				sum+=a[k];
				if(a[k]<0)
					fs[++tot]=a[k];//从右边取出j个数，并将负数加入到fs数组中
			}
			sort(fs+1,fs+tot+1);//将负数排序，就可以从小到大将负数丢掉
			int s=m-i-j;
			for(int k=1;k<=tot;k++){//枚举负数
				if(s==0) break;//不能超过步骤
				s--;
				sum-=fs[k];//将最小的负数丢掉
			}
			ans=max(ans,sum);//求出最大值
		}
	}
	cout<<ans;
	return 0;
}