题解：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;
}