CodeForces-1312E Array Shrinking

传送门：CodeForces-1312E

题目描述

You are given an array $a_1,a_2,…,a_n.$ You can perform the following operation any number of times:

• Choose a pair of two neighboring equal elements $a_i=a_{i+1}$ （if there is at least one such pair）.
• Replace them by one element with value $a_i+1$

After each such operation, the length of the array will decrease by one （and elements are renumerated accordingly）. What is the minimum possible length of the array $a$ you can get?

输入描述

The first line contains the single integer $n$ $(1≤n≤500)$ — the initial length of the array $a$.

The second line contains $n$ integers $a_1,a_2,…,a_n$ $(1≤a_i≤1000)$ — the initial array $a$

输出描述

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

思路分析

数据范围只有500，可以区间DP
$dp[i][j]$表示$i$到$j$这个区间最后剩下几个元素，还需要另一个数组来记录$i$到$j$剩下的元素是多少
然后枚举区间长度以及中间点，只有当左区间和右区间长度都为1的时候，且元素之间也符合关系，才能合并

样例输入

7
3 3 4 4 4 3 3

样例输出

2

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1111;

int dp[N][N],a[N][N];

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            dp[i][j]=j-i+1;
    for(int i=1; i<=n; i++) {
        cin>>a[i][i];
        dp[i][i]=1;
    }
    for(int len=2; len<=n; len++) {
        for(int l=1,r=l+len-1; r<=n; l++,r++) {
            for(int k=l; k<=r; k++) {
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
                if(dp[l][k]==1 && dp[k+1][r]==1 && a[l][k]==a[k+1][r]) {
                    dp[l][r]=1;
                    a[l][r]=a[l][k]+1;
                }
            }
        }
    }

    cout<<dp[1][n]<<endl;




    return 0;
}