传送门

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