洛谷P2545 [AHOI2004]实验基地

题目描述

输入输出格式

输入格式：

第一行有一个整数N(3<N<2000)，表示登陆地带的大小是2×N。随后的两行每一行有N个整数（其绝对值不超过10^6），表示对应的矩形土地的适用度评估值，各个整数之间用一个空格隔开。

输出格式：

只有一行输出，为整数M，即所确定的实验基地的适用度。

输入输出样例

输入样例#1： 

4
-1 2 -3 4
5 6 7 8

输出样例#1： 

31

这一题中n<=2000 所以可以想到O(N^2)

这一题的意思是在2*n的矩阵中找出权值和最大的U型，因为有负数，所以我们要找出最小的子段和

那么怎么求这个值呢？

我们可以定义一个s，不断的加当前位置的数，如果s的值变为是正数，那么肯定不是最有的，所以s重置为0

反之如果当前是数正数，不一定要断开这一段累加，因为s可能还是负数，如果后面也有负数，就对后面会有帮助

因此只有当s>0 的时候把s变为0

并且定义一个minn记录当前搜索的s的最小值，因为当前的s不一定是最优的，也没有必要用当前的s

如果看不懂这一段文字，那么代码一定能够帮助您

#include <iostream>

using namespace std ;

const int N = 2e3 + 10 ;

int n , a[N][2] ; 
int ans = -999999999 ; //ans记录全局最优解 

int main() {
	cin >> n ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i][0] ; //输入 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i][1] ;
	for ( int i = 1 ; i <= n - 2 ; i ++ ) {
		int now , minn = 0, s = 0 ; //min记录最小的s，now表示当前所有的和 
		now = a[i][0] + a[i][1] + a[i+1][0] + a[i+1][1] ;
		for ( int j = i + 2 ; j <= n ; j ++ ) {
			s += ( a[j-1][0] ) ; s = min ( s , 0 ) ; //累加，如果超过0就变为0 
			minn = min ( minn , s ) ; //记录最小值 
			now += a[j][0] + a[j][1] ; //累加一下 
			ans = max ( ans , now - minn ) ; //记录最大值 
		}
	}
	cout << ans << endl ; //输出 
	return 0 ;
}