【题解】AT3944 [ARC092C] Both Sides Merger([solution] at3944 [arc092c] both sides merge)

Sol

首先,答案肯定是原序列的一个子序列之和。
然后观察这个合并操作,很容易发现奇数位置只能与奇数位置合并,偶数位置只能与偶数位置合并。
那么问题转化为要在奇数位置上选一些数或者偶数位置上选一些数使他们和最大。
直接 dp 就行。
构造方案的话先删两端的,然后每次取中点一个一个合并即可。
时间复杂度 \(O(n^2)\)

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=5e3+10;
vector<int> G,Ans;
int n,a[N],dp[N],pre[N],ans,now,ff;
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
		if (a[i]>0) ff=1;
	}
	if (!ff)
	{
		int j=1;
		for (int i=1;i<=n;i++)
			if (a[i]>a[j]) j=i;
		writeln(a[j]); writeln(n-1);
		for (int i=1;i<j;i++)
			writeln(1);
		for (int i=n;i>j;i--)
			writeln(i-j+1);
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		dp[i]=a[i];
		for (int j=i-2;j>=1;j-=2)
			if (dp[j]+a[i]>dp[i]) dp[i]=dp[j]+a[i],pre[i]=j;
	}
	for (int i=1;i<=n;i++)
		if (ans<dp[i]) ans=dp[i],now=i;
	writeln(ans);
	while (pre[now])
	{
		G.push_back(now);
		now=pre[now];
	}
	G.push_back(now);
	reverse(G.begin(),G.end());
	for (int i=1;i<G[0];i++)
		Ans.emplace_back(1);
	int tot=G[0]-1;
	for (int i=n;i>=G[G.size()-1]+1;i--)
		Ans.emplace_back(i-tot);
	for (int i=0;i<(int)G.size()-1;i++)
	{
		int X=G[i+1]-G[i]+1-1;
		if (G[i+1]-G[i]==2)
		{
			Ans.emplace_back(2);
			continue;
		}
		for (int j=G[i]+1;j<G[i+1]-1;j+=2)
			Ans.emplace_back(3);
		Ans.emplace_back(2);
		tot+=X;
	}
	writeln(Ans.size());
	for (auto x:Ans)
		writeln(x);
}





————————

Sol

First, the answer must be the sum of a subsequence of the original sequence.
Then observe the merging operation. It is easy to find that odd positions can only be merged with odd positions, and even positions can only be merged with even positions.
Then the problem is to choose some numbers in odd positions or some numbers in even positions to maximize their sum.
Just DP.
For the construction scheme, delete the at both ends first, and then merge one midpoint at a time.
Time complexity \ (O (n ^ 2) \)

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=5e3+10;
vector<int> G,Ans;
int n,a[N],dp[N],pre[N],ans,now,ff;
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
		if (a[i]>0) ff=1;
	}
	if (!ff)
	{
		int j=1;
		for (int i=1;i<=n;i++)
			if (a[i]>a[j]) j=i;
		writeln(a[j]); writeln(n-1);
		for (int i=1;i<j;i++)
			writeln(1);
		for (int i=n;i>j;i--)
			writeln(i-j+1);
		return 0;
	}
	for (int i=1;i<=n;i++)
	{
		dp[i]=a[i];
		for (int j=i-2;j>=1;j-=2)
			if (dp[j]+a[i]>dp[i]) dp[i]=dp[j]+a[i],pre[i]=j;
	}
	for (int i=1;i<=n;i++)
		if (ans<dp[i]) ans=dp[i],now=i;
	writeln(ans);
	while (pre[now])
	{
		G.push_back(now);
		now=pre[now];
	}
	G.push_back(now);
	reverse(G.begin(),G.end());
	for (int i=1;i<G[0];i++)
		Ans.emplace_back(1);
	int tot=G[0]-1;
	for (int i=n;i>=G[G.size()-1]+1;i--)
		Ans.emplace_back(i-tot);
	for (int i=0;i<(int)G.size()-1;i++)
	{
		int X=G[i+1]-G[i]+1-1;
		if (G[i+1]-G[i]==2)
		{
			Ans.emplace_back(2);
			continue;
		}
		for (int j=G[i]+1;j<G[i+1]-1;j+=2)
			Ans.emplace_back(3);
		Ans.emplace_back(2);
		tot+=X;
	}
	writeln(Ans.size());
	for (auto x:Ans)
		writeln(x);
}