洛谷P2545 [AHOI2004]实验基地

题目描述

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

4
-1 2 -3 4
5 6 7 8

输出样例#1：

这一题中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 ;
}

然而这不是最快的，其实还有一个O（n）的做法，即使n有几千万都不怕（记得加快读，cin中看不中用）

我们定义5个状态：

该列不选且之前未建过实验基地。
该列不选且之前已经建完实验基地。
该列全选且未建过样品采集区。
该列全选且已建过样品采集区。
该列选下面一行（上面建样品采集区）

状态继承也很简单：

dp[i][1] = dp[i-1][1] ;
dp[i][2] = max ( dp[i-1][2] , dp[i-1][4] ) ;
dp[i][3] = max ( dp[i-1][1] , dp[i-1][3] ) + a[i][0] + a[i][1] ;
dp[i][4] = max ( dp[i-1][4] , dp[i-1][5] ) + a[i][0] + a[i][1] ;
dp[i][5] = max ( dp[i-1][3] , dp[i-1][5] ) + a[i][1] ;

这个继承是很好看懂的，我就不多说了，上一个代码（加滚动数组优化）

#include <iostream>using namespace std ;const int N = 2e3 + 10 ;int n , a[N][2] ; 
int dp[2][7] ;  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] ;dp[1][1] = 0 ; dp[1][3] = a[1][0] + a[1][1] ;dp[1][2] = dp[1][4] = dp[1][5] = -999999999 ;for ( int i = 2 ; i <= n ; i ++ ) {dp[i&1][1] = dp[i&1^1][1] ;dp[i&1][2] = max ( dp[i&1^1][2] , dp[i&1^1][4] ) ;dp[i&1][3] = max ( dp[i&1^1][1] , dp[i&1^1][3] ) + a[i][0] + a[i][1] ;dp[i&1][4] = max ( dp[i&1^1][4] , dp[i&1^1][5] ) + a[i][0] + a[i][1] ;dp[i&1][5] = max ( dp[i&1^1][3] , dp[i&1^1][5] ) + a[i][1] ;}cout << max ( dp[n&1][2] , dp[n&1][4] ) << endl ;return 0 ;
}

给大家留一个问题：

请问为什么O(N^2)代码比O(N)的代码快？快在何处？