P9744 「KDOI-06-S」消除序列

题目

link

题解

考虑dp

设f[i]表示使序列由全是1到满足集合$P$条件所需的最少代价

然后想一想，f[i]怎么推

首先，我们可以把p[i]之前的全部推平，都变成$0$，然后一个一个变成1

其次，我们也可以把f[i - 1]搞出来，然后把p[i - 1] + 1到p[i] - 1之间都弄成$0$。

这里就只能进行若干次第二次操作了，可以用前缀和来优化

但是“首先”一条的复杂度这么做肯定太高，因此再设g[i]表示使序列由全是$0$到满足集合$P$条件所需的最少代价。

状态转移方程在代码里（

锅

考场上想到有可能要用dp，但没接着想下去。而是想贪心性质去了（但是好像可以用贪心做，等几天看看别的题解）

还真有
https://www.luogu.com.cn/blog/Pretharp/p9744-ti-xie

继而可得，我们需要归零的前缀的末尾必然是在某一个将要变为 1 的位置的前面一个位置，显然可以直接对于每个询问 O(m) 枚举得到答案。时间复杂度 O(n+mq)

代码

#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;
//O(nq)的算法肯定超时，又因为提供了∑m，所以考虑可以O(qm)のdp 
int f[N], g[N];//f_i表示把序列[1, 1, 1, 1, 1.....]变成满足前p_i个数所需要的最小代价 
//但是发现——似乎没法快速转移，于是 令 g_i表示把序列[0, 0, 0, 0, 0.....]变成满足前p_i个数所需要的最小代价 
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;
}