P2545 [AHOI2004]实验基地 题解

· · 题解

原题

序

看到题解里大多都是 O(n^2) 的，其实这道题的 O(n) 解法还是非常有思维难度的。

题意

分析

对于每个凹形块，我们可以将他分成三部分，分别是左边上下两行都选择的部分，中间只选第二行的部分，以及右边上下两行都选择的部分，然后考虑分三个阶段进行 dp。

做法

用 a_{i,0} 表示第 1 行第 i 个元素，用 a_{i,1} 表示第 2 行第 i 个元素，f_{i,0} 表示到第 i 列为止的左边部分的元素的和的最大值，f_{i,1} 表示到第 i 列为止的左、中部分的元素的和的最大值，f_{i,2} 表示到第 i 列为止的左、中、右部分的元素的和的最大值，所以我们可以得到以下状态转移方程：

f_{i,0}=max(f_{i-1,0},0)+a_{i,0}+a_{i,1} f_{i,1}=max(f_{i-1,0},f_{i-1,1})+a_{i,0} f_{i,2}=max(f_{i-1,1},f_{i-1,2})+a_{i,0}+a_{i,1}

因为每个状态都是由上一个状态转移来的，而且要选择的是非空矩形，f_{i,0}=f_{i,1}=f_{i,2}=-\infty

代码

#include<cstdio>
#include<algorithm> 
#define N 5000001
#define inf 1e9
#define ll long long

using namespace std;

int n,a[N][2],f[N][3];
ll ans=-inf;

int main(){
    scanf("%d",&n);
    if(n<=2){
        printf("0");
        return 0;
    } // 题目中提到的凹形块的 w1 要大于2 
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i][0]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i][1]);
    f[0][0]=f[0][1]=f[0][2]=-inf; 
    for(int i=1;i<=n;i++){
        f[i][0]=max(f[i-1][0],0)+a[i][0]+a[i][1];
        f[i][1]=max(f[i-1][0],f[i-1][1])+a[i][1];
        f[i][2]=max(f[i-1][1],f[i-1][2])+a[i][0]+a[i][1]; // dp
        ans=max(ans,1ll*f[i][2]); // 取最大结果 
    }
    printf("%lld",ans);
    return 0;
}