题解：P12687 [KOI 2022 Round 1] 鹅卵石

原题链接

• 洛谷 P12687 [KOI 2022 Round 1] 鹅卵石

题意简述

给定长度为 $n$ 的数组 $a$，每次可对相邻两点同时拿相同数量，或对单点拿任意数量，求将所有石子拿完时所需的最少操作次数。

解题思路

1. 枚举每个起点 $i$，向右模拟交替相邻配对：维护一个变量 $t$，初始为 $a_i$，然后依次计算 $t=a_j-t$。

2. 若 $t>0$ 且恰好等于 $a_{j+1}$，则区间 $[i,j+1]$ 可以完全通过相邻配对消除，记录其右端点为 $j$。否则若 $t\le 0$ 则跳出，尝试下一个起点。

3. 令 $f_i$ 表示在位置 $[1,i+1]$ 范围内，最多能选的互不重叠“可消除区间”数量。

4. 对每个右端点 $i$，先继承 $f_{i-1}$（不选任何以 $i$ 结尾的区间），再遍历所有以 $i$ 为右端的合法起点 $u$，计算其对应候选值 $f_{u-2}+1$（若 $u=1$ 则为 $1$），取最大更新 $f_i$。

5. 最大可配对消除区间数为 $f_{n-1}$，剩下必须单点拿的次数即 $n-f_{n-1}$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=2505;
int a[N],f[N];
vector<int> G[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		int t=a[i];
		for(int j=i;j<n;j++)
		{
			if(j>i)t=a[j]-t;
			if(t<=0)break;
			if(t==a[j+1])G[j].push_back(i);
		}
	}
	for(int i=1;i<n;i++)
	{
		f[i]=f[i-1];
		for(auto u:G[i])
		{
			f[i]=max(f[i],u==1?1:f[u-2]+1);
		}
	}
	cout<<n-f[n-1]<<'\n';
	return 0;
}