题解 P2545 【[AHOI2004]实验基地】
给大家推荐一下:MyBlog
这一题中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个状态 ：
1.该列不选且之前未建过实验基地。
2.该列不选且之前已经建完实验基地。
3.该列全选且未建过样品采集区。
4.该列全选且已建过样品采集区。
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)的代码快？快在何处？