1
2
3
4
5
6
7
8
9
10
11
12
13

long long ans = 0;
for(int len = 2; len<=N; len++){
    for(int i = 1; i+len-1<=N; i++){
        int y = i+len-1;
        for(int k = i; k<y; k++){
            if(DP[i][k] == DP[k+1][y]){
                DP[i][y] = max(DP[i][y], DP[i][k] + 1);
            }
        }
        ans = max(ans, DP[i][y]);
    }
}
cout << ans << endl;

1
2
3

f[i][j] = f[i-1][f[i-1][j]];

把 f[i][j] 拆分成兩個能合成為 i-1 的區間

1
2
3
4
5

                 f[i-1][j]
    |------<i-1>-----|----<i-1>-----|
    j                      f[i-1][f[i-1][j]] 

如果 f[i-1][j] 或 f[i-1][f[i-1][j]] 不成立，f[i][j] 就不成立，即轉移為 0

1
2
3
4
5
6
7
8
9
10

for(int i =2; i<=58; i++){
    for(int j = 1; j<=N; j++){
        if(!DP[i][j]){
            DP[i][j] = DP[i-1][DP[i-1][j]];
        }
        if(DP[i][j]){
            ans = i;
        }
    }
}

1
2
3
4
5

for(int i = 1; i<=N; i++){
    int in;
    cin >> in;
    DP[in][i] = i+1;
}