题解：P9180 [COCI2022-2023#5] Slastičarnica

· · 题解

P9180 [COCI2022-2023#5] Slastičarnica 题解

题面

题意

我觉得出题人说的已经很像人话了，我就不再赘述了（其实我读了两遍）。

思路

  1. 但凡你有点脑子（我没脑子）就能看出来 1\le q\le2\times 10^5 这个数据范围就是个诈骗，因为你最多删除 n 个数，所以你最多执行 \min(n,q) 次操作，所以直接让 q=\min(n,q)。

  2. 然后……肯定直接区间 DP 上（简单粗暴），然后直接拿下全场最劣解。

dp方程

先预处理，对于第 i 个操作，用一个 vector 存下满足要求的所有区间

懒得写 latex 了，直接对着代码讲，对于 dp_{i,j} 

int l=*lower_bound(v[dp[i][j]+1][0].begin(),v[dp[i][j]+1][0].end(),i);//从左边取能拿到的最近的满足下一个要求的位置
int r=*--upper_bound(v[dp[i][j]+1][1].begin(),v[dp[i][j]+1][1].end(),j);//从右边取能拿到的最近的满足下一个要求的位置
if(l+d[dp[i][j]+1]-1<=j)//判断满足要求的区间是否超出 i~j 这个范围
{
    dp[l+d[dp[i][j]+1]][j]=max(dp[l+d[dp[i][j]+1]][j],dp[i][j]+1);
    maxx=max(maxx,dp[l+d[dp[i][j]+1]][j]);//统计答案
}
if(r-d[dp[i][j]+1]+1>=i)//判断满足要求的区间是否超出 i~j 这个范围
{
    dp[i][r-d[dp[i][j]+1]]=max(dp[i][r-d[dp[i][j]+1]],dp[i][j]+1);
    maxx=max(maxx,dp[r-d[dp[i][j]+1]][j]);//统计答案
}

code

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define endl '\n'

const int maxn=5010;
int n,q;
int a[maxn];
int d[maxn],s[maxn];
vector<int>v[maxn][2];
int dp[maxn][maxn];

signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
//  ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(q>n)
    {
        q=n;
    }
    for(int i=1;i<=q;i++)
    {
        cin>>d[i]>>s[i];
    }
    for(int i=1;i<=q;i++)
    {
        int p=1;
        v[i][0].push_back(0);
        for(int j=1;j<=n;j++)
        {
            if(a[j]<s[i])
            {
                p=j+1;
            }
            else if(j-p+1>=d[i])
            {
                v[i][0].push_back(p);
                p++;
            }
        }
        v[i][0].push_back(n+1);
        p=n;
        v[i][1].push_back(n+1);
        for(int j=n;j>=1;j--)
        {
            if(a[j]<s[i])
            {
                p=j-1;
            }
            else if(p-j+1>=d[i])
            {
                v[i][1].push_back(p);
                p--;
            }
        }
        v[i][1].push_back(0);
        reverse(v[i][1].begin(),v[i][1].end());
    }


//  for(int i=1;i<=q;i++)
//  {
//      cout<<"i="<<i<<endl;
//      cout<<"1:\n";
//      for(int j:v[i][0])
//      {
//          cout<<j<<' ';
//      }
//      cout<<endl;
//      cout<<"2:\n";
//      for(int j:v[i][1])
//      {
//          cout<<j<<' ';
//      }
//      cout<<endl;
//  }


    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=n;j>=i;j--)
        {
            int l=*lower_bound(v[dp[i][j]+1][0].begin(),v[dp[i][j]+1][0].end(),i);
            int r=*--upper_bound(v[dp[i][j]+1][1].begin(),v[dp[i][j]+1][1].end(),j);
            if(l+d[dp[i][j]+1]-1<=j)
            {
                dp[l+d[dp[i][j]+1]][j]=max(dp[l+d[dp[i][j]+1]][j],dp[i][j]+1);
                maxx=max(maxx,dp[l+d[dp[i][j]+1]][j]);
            }
            if(r-d[dp[i][j]+1]+1>=i)
            {
                dp[i][r-d[dp[i][j]+1]]=max(dp[i][r-d[dp[i][j]+1]],dp[i][j]+1);
                maxx=max(maxx,dp[r-d[dp[i][j]+1]][j]);
            }
        }
    }
    cout<<maxx<<endl;
    return 0;
}