题解 P2545 【[AHOI2004]实验基地】

· · 题解

好像都是n^2的算法？来一发O(n)的

（好吧，可能是数据太水）

首先，考虑对于一列5个状态

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

然后状态转移。

f[i][1]=f[i-1][1];//其实没必要，懒得删。
f[i][2]=max(f[i-1][2],f[i-1][4]);
f[i][3]=max(f[i-1][3],f[i-1][1])+上下;
f[i][4]=max(f[i-1][4],f[i-1][5])+上下;
f[i][5]=max(f[i-1][5],f[i-1][3])+下;

最后输出max(f[n][2],f[n][4])

然后莫名其妙就AC了。

下附代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#define NO -0xfffffff
using namespace std;
int f[1010][5];
int num[1010][2];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&num[i][0]);
    for(int i=0;i<n;i++)
    scanf("%d",&num[i][1]);
    f[0][0]=0;f[0][1]=num[0][0]+num[0][1];f[0][2]=f[0][3]=f[0][4]=NO;
    for(int i=1;i<n;i++)
    {
        f[i][0]=f[i-1][0];
        f[i][1]=max(f[i-1][1],f[i-1][0])+num[i][0]+num[i][1];
        f[i][2]=max(f[i-1][1],f[i-1][2])+num[i][1];
        f[i][3]=max(f[i-1][3],f[i-1][2])+num[i][0]+num[i][1];
        f[i][4]=max(f[i-1][3],f[i-1][4]);
    }
    printf("%d",max(f[n-1][3],f[n-1][4]));
    return 0;
}

如果有大佬发现问题可以发评论（毕竟n=1000···）