洛谷 P1121 环状最大两段子段和 题解【DP】【环形】
点击量：343
典型的动态规划类题目，不过这次在环上，而且是两端，所以DP方法要有所改进。
题目描述
给出一段环状序列，即认为$ A_1$和$ A_n$是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。
输入输出格式
输入格式：
第一行是一个正整数$ n(n\le 2\times 10^5)$，表示了序列的长度。
第二行包含n个绝对值不大于的整数$ A_i$ ，描述了这段序列，第一个数和第n个数是相邻的。
输出格式：
一个整数，为最大的两段子段和是多少。
输入输出样例
输入样例#1：72 -4 3 -1 2 -4 3输出样例#1：9
这个题首先看上去是想切环为链，但是发现不是很好控制长度，于是改为做两次，第一次是找不越界的，求最大值。第二次是找不越界的求最小值，也就是这样：
（红色表示被选的块，它们最大）
（红色表示被选的块，而此时蓝色最小）
这样就避免了切环为链，也方便理解，而且它就是两段。
重点在于 不能只选一个点，也不能一个点都不选，所以状态转移方程的状态中细节是很多的。
针对上面的状况，我们把第一段的状态定为1，第二段的状态定为3，第一段与第二段中间的状态为2，最开始没有被选的是0，而最后一段不能为0，不然会出现这种情况：
5 -4 6 -7 4 -3 9
当状态3结束后，后面的状态是0，但是1也可以从0转移过来，这样序列中就会有无限的1，3，1，3……了。答案总是所有正数之和。
最终的答案要从所有点的状态3找最值。（第一遍找的是最大值，第二遍找的是最小值。）
- 首先，我们的dp数组初始化应为$ -\infty$。
- 我们在转移的过程中，两段是可以连续的，所以3可以从1转移过来。除此之外，2只能从1转移，1从0和1转移，3从1，2，3转移
- 在第二遍做时，因为不能一个都不选，所以状态枚举是从1到n-1的。
不愧是紫题难度，解题思路也是非常难想的，细节颇多。
Code：
#include<cstdio>
#include<cstring>
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
int a[202500];
int f[202500][4];
int main()
{
int n,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
memset(f,-0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
{
f[i][0]=f[i-1][0];
f[i][1]=max(f[i-1][0],f[i-1][1])+a[i];
f[i][2]=max(f[i-1][1],f[i-1][2]);
f[i][3]=max(max(f[i-1][1],f[i-1][2]),f[i-1][3])+a[i];
}
int ans=-9999999;
for(int i=1;i<=n;i++)
{
if(f[i][3]>ans)
ans=f[i][3];
}
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)//取两段最小的
{
f[i][0]=f[i-1][0];
f[i][1]=min(f[i-1][0],f[i-1][1])+a[i];
f[i][2]=min(f[i-1][1],f[i-1][2]);
f[i][3]=min(min(f[i-1][1],f[i-1][2]),f[i-1][3])+a[i];
}
int minn=9999999;
for(int i=1;i<n;i++)//如果全为负，那么f[n][3]一定是sum，不合题意
if(f[i][3]<minn)
minn=f[i][3];
ans=max(ans,sum-minn);
printf("%d\n",ans);
return 0;
}
… [Trackback]
[…] Read More to that Topic: wjyyy.top/321.html […]
… [Trackback]
[…] Read More here on that Topic: wjyyy.top/321.html […]