P9744 "KDOI-06-S" Elimination Sequence

Title#

link

Solution#

Consider dp

Let f[i] represent the minimum cost required to transform the sequence from all 1s to satisfy the set $P$ conditions.

Then think about how to derive f[i].

First, we can flatten all elements before p[i], turning them all into $0$, and then change them to 1 one by one.

Secondly, we can also derive f[i - 1], and then turn all elements between p[i - 1] + 1 and p[i] - 1 into $0$.

Here we can only perform several second operations, which can be optimized using prefix sums.

However, the complexity of the "first" operation is definitely too high, so we define g[i] to represent the minimum cost required to transform the sequence from all $0$s to satisfy the set $P$ conditions.

The state transition equation is in the code (

Pot#

I thought during the exam that I might need to use dp, but I didn't continue thinking. Instead, I thought about the greedy property (but it seems it can be done greedily, will check other solutions in a few days).

Indeed there is
https://www.luogu.com.cn/blog/Pretharp/p9744-ti-xie

Consequently, we can deduce that the end of the prefix we need to zero out must be right before a position that will become 1, and we can directly enumerate the answer for each query in O(m). The time complexity is O(n+mq).

Code#

#include<bits/stdc++.h>
const int N = 5e5 + 10;
using namespace std;
#define int long long
int a[N], b[N], c[N];
int n;
// The O(nq) algorithm will definitely time out, and since ∑m is provided, we consider an O(qm) dp 
int f[N], g[N];// f_i represents the minimum cost to transform the sequence [1, 1, 1, 1, 1.....] to satisfy the first p_i numbers 
// but it seems there is no quick transition, so let g_i represent the minimum cost to transform the sequence [0, 0, 0, 0, 0.....] to satisfy the first p_i numbers 
int p[N], m;
int b_sum[N]; 
signed main()
{
	scanf("%lld", &n);
	for(int i = 1;i <= n;i++)
		scanf("%lld", &a[i]);
	for(int i = 1;i <= n;i++)
		scanf("%lld", &b[i]), b_sum[i] = b_sum[i - 1] + b[i];
	for(int i = 1;i <= n;i++)
		scanf("%lld", &c[i]);

	for(int i = 2;i <= n;i++)
		a[i] = min(a[i - 1] + b[i], a[i]);
	int q;
	scanf("%lld", &q);

	while(q --)
	{
		scanf("%lld", &m);
		for(int i = 1;i <= m;i++)
		{
			scanf("%lld", &p[i]);
		}

		for(int i = 1;i <= m;i++)
		{
			g[i] = g[i - 1] + c[p[i]];
			f[i] = a[p[i] - 1] + g[i - 1];
			f[i] = min(f[i], f[i - 1] + b_sum[p[i] - 1] - b_sum[p[i - 1]]);
		}
		printf("%lld\n", min(g[m] + a[n], f[m] + b_sum[n] - b_sum[p[m]]));
	}
	return 0;
}