题解：CF1312E Array Shrinking

cff_0102 · 2024-10-29 11:12:19 · 题解

不同于其它题解的 dp 做法。

考虑状态 i,j 表示将前 i 个数进行若干次合并操作，且最终得到的最右侧的数是 j。

设 dp_{i,j} 表示达到状态 i,j 时，最右侧的这个数由几个数合并而来，ans_{i,j} 表示此时 1\sim i 最少合并为几个数，mn_i=\min_{j}(ans_{i,j})，其中状态 i,j 合法。

每次遍历到一个新的数 i 的时候，可以选择：

• 不与前面的数合并，则 dp_{i,a_i}=1，mn_{i}=ans_{i,a_i}=mn_{i-1}+1。
• 与前面的数合并：
  1. 首先，设 x=a_i,l=i-1。
  2. 如果 dp_{l,x} 不为 0，即状态 (l,x) 可达，因此可以将现在的数 x 和前面的状态 l,x 最右边的 x 合并。现在的 x 变为 x+1，l 变为 l-dp_{l,x}，并继续重复这一步，尝试与更前面的数合并（并分别把答案保存在 dp_{i,x} 和 ans_{i,x} 中），直到 dp_{l,x}=0，则不能继续合并。

最后输出 mn_i 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int a[N];
int dp[N][N<<1],ans[N][N<<1],mn[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        int x=a[i];
        dp[i][x]=1;
        mn[i]=ans[i][x]=mn[i-1]+1;
        int l=i-1;
        while(dp[l][x]){
            dp[i][x+1]=i-(l-dp[l][x]);
            ans[i][x+1]=ans[l][x];
            mn[i]=min(mn[i],ans[i][x+1]);
            l-=dp[l][x];
            x++;
        }
    }
    cout<<mn[n];
    return 0;
}