自动搬运

查看原文

来自洛谷，原作者为

	Flying2018 **

搬运于2025-08-24 21:38:53，当前版本为作者最后更新于2018-09-22 22:03:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像都是$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···）