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

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

### 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;
}
{
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);
for (int i=1;i<=n;i++)
{
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;
}
{
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);
for (int i=1;i<=n;i++)
{
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);
}

``````