猫史档案馆

用户:

寂寞de奶酪查看:0 回复:1 评论:0 创建时间:2023-07-22T21:07:33

题目背景

小T对手工很感兴趣，立志成为一名工匠。他一到暑假就会到自家开的工厂里帮工人师傅打下手，学习一些身为工匠应具备的技能。

题目描述

有一条由 n个钢圈组成的钢条，将钢圈按 1∼n 编号。其中一些钢圈有损坏，小T依次测量了每个钢圈的健康度，健康度为正数的是没有损坏的钢圈，为负数的说明有损坏且数字越小损坏程度越严重。

现在小T要用手头上已有的工具和材料对钢条进行修复，但是受限于修复的技术，小T只能修复连续的一整段钢圈，这段钢圈的起点 x 和终点 y 可以任意选择（必须至少对一节钢圈进行修复）。经过修复后，这些钢圈的健康度会变为相反数，也就是负数变正数，正数变负数。

为了使得修复的效果尽可能好，小T需要使得修复后整段钢条的总健康度最大。请你帮小T计算一下修复后整段钢条的总健康度最大是多少？

输入格式

第一行一个整数 n，表示钢圈数量

第二行 n 个整数ai，对应每个钢圈的健康度

输出格式

一个整数，符合题目要求的答案

样例数据输入样例 #1

6
-1 7 -4 -2 5 -8

输出样例 #1

样例解释

样例一中，小T选择修复 [3,6] 这段钢圈，修复后整体健康度变为 -1 7 4 2 -5 8，此时总健康度为 15。是所有修复方案中最优的。

数据范围

对于 10% 的数据，1≤n a≤1000

对于 50% 的数据，1≤n≤100

对于 100% 的数据，

一只小枫鸽

#include <bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005];
pair<int,int> lsi(int l,int r){
	if (l==r)
	  return make_pair(l,r);
	int sum1=0,sum2=0,sum3=0,lsum;
	int l1=lsi(l,(r-l)/2+l).first,r1=lsi(l,(r-l)/2+l).second;
	int l2=lsi((r-l)/2+l+1,r).first,r2=lsi((r-l)/2+l+1,r).second;
	for (int i=l1;i<=r1;i++)
	  sum1+=b[i];
	for (int i=l2;i<=r2;i++)
	  sum2+=b[i];
	for (int i=r1+1;i<l2;i++)
	  sum3+=b[i];
	lsum=max(sum1,sum2);
	lsum=max(lsum,sum3);
	if (lsum==sum1)
	  return make_pair(l1,r1);
	if (lsum==sum2)
	  return make_pair(l2,r2);
	if (lsum==sum3)
	  return make_pair(r1+1,l2-1);
}
int main(){
	cin>>n;
	for (int i=0;i<n;i++){
		cin>>a[i];
		b[i]=0-a[i];
	}
	int l=lsi(0,n-1).first,r=lsi(0,n-1).second,ans=0;
	for (int i=l;i<=r;i++)
	  a[i]=0-a[i];
	for (int i=0;i<n;i++)
	  ans+=a[i];
	cout<<ans;
}

样例过了

猫史档案馆

C++题目

回复