【CF1312E】Array Shrinking（dp）

传送门

• 题目：
  
• 思路：
  数组中的某些数可以通过执行多次题目中的操作最终归为1个数。
  先确定每个 $r(1\le r\le n)$r(1≤r≤n)有哪些 $l(1\le l\le r)$l(1≤l≤r)满足 $[l,r]$[l,r]内的数可以归为1个数。在处理的时候可以先枚举 $l$l，这样 $r$r每次都只增加1。且 $[l,oldr]$[l,oldr]的结果已知， $[l,newr]$[l,newr]只是在 $[l,oldr]$[l,oldr]在多考虑一个数字而已，用栈模拟。
  $dp\left[i\right]$dp[i]表示 $[1,i]$[1,i]内可以形成的答案数， $dp\left[i\right]=min\left\{dp\right[j-1]+1\}$dp[i]=min{dp[j−1]+1}，其中j是由前面的处理得到的满足 $[j,i]$[j,i]内的数能归为1个数的下标。
  最终答案是 $dp\left[n\right]$dp[n]，时间复杂度 $O\left(n^2\right)$O(n2)
• ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 550;
const ll mod = 998244353;
int n;
int dp[maxn], a[maxn];
vector<int> v[maxn];
stack<int> s;
bool check(int x)
{
    while(!s.empty() && s.top()==x)
    {
        x = x+1;
        s.pop();
    }
    s.push(x);
    if(s.size()==1) return true;
    else return false;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int l = 1; l <= n; l++)
    {
        while(!s.empty()) s.pop();
        for(int r = l; r <= n; r++)
            if(check(a[r])) v[r].push_back(l);
    }
    for(int i = 1; i <= n; i++) dp[i] = INT_MAX;
    for(int r = 1; r <= n; r++)
        for(auto l : v[r])
            dp[r] = min(dp[r], dp[l-1]+1);
    printf("%d\n", dp[n]);
    return 0;
}