【CF933E】A Preponderant Reunion（动态规划）

题面

题解

直接做很不好搞，我们把条件放宽，我们每次可以选择两个相邻的非零数让他们减少任意值，甚至可以减成负数（虽然你肯定不会把它弄成负数的）。代价为减少的值。不难证明这个问题的答案不会优于原题目。

我们假定只处理\([l,r]\)这段区间的数\(p_l,p_{l+1},...,p_r\)的答案，为了方便，我们假定数列开头结尾都是\(0\)。

我们令\(c_l=p_l,c_i=\max\{p_i-c_{i-1},0\}\)，那么我们必定可以构造一种方案，使得处理这一段区间使得所有数都变成非负数的代价为\(\sum c_i\)。然后设\(f[l][r]\)为这个值。

\[\begin{aligned}
f[l][r]&=f[l][r-2]+c_{r-1}+c_r\\
&=f[l][r-2]+c_{r-1}+\max\{p_r-c_{r-1},0\}\\
&=f[l][r-2]+\max\{p_r,c_{r-1}\}\\
&\ge f[l][r-2]+p_r\\
&=f[l][r-2]+f[r][r]
\end{aligned}\]

所以一个区间\([l,r]\)可以拆分成\([l,r-2]\)这个区间的打啊，然后是\(r-1\)保留为正数，\([r,r]\)这个区间的答案。然后递归处理前面这一段区间，我们得到的就是每次可以拆分出\(2\)个或者\(1\)个位置使得他们变成\(0\)，有\(2\)的原因是当区间长度为\(2\)的时候不得不使得两个位置都是\(0\)而不能拆分。

于是我们就考虑每次放\(0\)段的长度，这个长度可以是\(1\)或者\(2\)，然后大力转移一下就可以。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 300300

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int n,p[MAX],g[MAX];ll f[MAX];

vector<int> Ans;

void Work(int i){int x=min(p[i],p[i+1]);if(!x)return;Ans.push_back(i);p[i]-=x;p[i+1]-=x;}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)p[i]=read();

	memset(f,63,sizeof(f));f[0]=0;

	for(int i=1;i<=n;++i)

	{

		f[i]=min(f[max(i-2,0)]+p[i],f[max(i-3,0)]+max(p[i],p[i-1]));

		if(f[i]==f[max(i-3,0)]+max(p[i],p[i-1]))g[i]=1;

	}

	ll ans=min(f[n],f[n-1]);

	for(int i=n-(ans==f[n-1]);i>0;i=i-2-g[i])

	{

		Work(i-1);if(g[i])Work(i-2);Work(i);

	}

	printf("%d\n",(int)Ans.size());

	for(int v:Ans)printf("%d\n",v);

	return 0;

}

巴特西

【CF933E】A Preponderant Reunion（动态规划）

【CF933E】A Preponderant Reunion（动态规划）

题面

题解

最新文章

热门文章