Educational Codeforces Round 83 (Rated for Div. 2)E. Array Shrinking【DP】

E. Array Shrinking
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array a1,a2,…,ana1,a2,…,an. You can perform the following operation any number of times:

Choose a pair of two neighboring equal elements ai=ai+1ai=ai+1 (if there is at least one such pair).

Replace them by one element with value ai+1ai+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 aa you can get?
Input
The first line contains the single integer nn (1≤n≤5001≤n≤500) — the initial length of the array aa.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000) — the initial array aa.
Output
Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.
Examples
input
Copy

5
4 3 2 2 3

output
Copy

2

input
Copy

7
3 3 4 4 4 3 3

output
Copy

2

input
Copy

3
1 3 5

output
Copy

3

input
Copy

1
1000

output
Copy

1

Note
In the first test, this is one of the optimal sequences of operations: 44 33 22 22 33 →→ 44 33 33 33 →→ 44 44 33 →→ 55 33.
In the second test, this is one of the optimal sequences of operations: 33 33 44 44 44 33 33 →→ 44 44 44 44 33 33 →→ 44 44 44 44 44 →→ 55 44 44 44 →→ 55 55 44 →→ 66 44.
In the third and fourth tests, you can't perform the operation at all.
 
 
제목: n개수, 만약에 a[i]==a[i+1]이면 이 두 개수를 a[i]+1으로 바꿀 수 있습니다. 조작 횟수가 무한하고 수조의 최단 길이가 얼마인지 물어보세요.
분석: 우선 구간 DP는 각 구간이 길이 1이 될 수 있는지를 찾아낸 다음에 문제는 1이 될 수 있는 몇몇 구간 중에서 가장 적은, 두 개의 겹치지 않는 구간을 골라 전체 수조를 덮어쓰는 것이다.

#include 
using namespace std;
int a[504];
int dp[504][504];
int dp2[504];
int main(){
    int n;
    cin>>n;
    memset(dp,0,sizeof(dp));
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        dp[i][i]=a[i];
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i <= n; ++i) {
            int j = i+len-1;
            if(j>n)break;
            for (int k = i; k < j; ++k) {
                if(dp[i][k]&&dp[k+1][j]){
                    if(dp[i][k] == dp[k+1][j]){
                        dp[i][j]=dp[k+1][j]+1;
                        break;
                    }
                }
            }
        }
    }
    memset(dp2,0x3f, sizeof(dp2));
    dp2[0]=0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            if(dp[j][i]){
                dp2[i]=min(dp2[i],dp2[j-1]+1);
            }
        }
    }
    cout<