CF1312 E. Array Shrinking

发表于 | 阅读数

一个数列相邻且相同的数可以合成其数+1，问最小能合多小。

$dp[i][j]$,是$[i,j]$是否合成一个数且值为$dp[i][j]$。一遍区间$dp$就可以把已知能合成的区间全部记录下来。

假设答案$ans[i]$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 5e2 + 10;
const int mod = 1e9 + 7;

int f[N][N];
vector<int> g[N];
int a[N], cnt, n, ans[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        f[i][i] = a[i];
        g[i].push_back(i);
    }
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            for (int t = i; t < j; t++)
                if (f[i][t] == f[t + 1][j] && f[i][t] != 0)
                    f[i][j] = f[i][t] + 1, g[j].push_back(i);
        }

    int st = 1;
    for (int i = 1; i <= n; i++)
    {
        ans[i] = ans[i - 1] + 1;
        for (int j = 0; j < g[i].size(); j++)
            ans[i] = min(ans[i], ans[g[i][j] - 1] + 1);
    }
    printf("%d\n", ans[n]);
}