题目链接

题面

题目描述

Matryoshkas 指一套传统的，尺寸从小到大套在一起的俄罗斯木娃娃。

一套 Matryoshka 娃娃可以被打开，以便观察其内部一个确定的较小排列。这个排列内部又有更小的一种排列，如此继续下去。

俄罗斯套娃博物馆最近展出了一些类似设计的俄罗斯套娃，它们的唯一不同只是每组套娃内含娃娃的数量。

不幸的是，一些“热心”的（并且显然没有大人监督的）孩子把这些套在一起的娃娃分开，把所有的单个的套娃放在了一排。在这一排中有n个娃娃，每个都有一个整数的大小。你需要在不知道原来的套娃的数量和排列方式的情况下，重新组装这些娃娃。你只知道，每一个完整的套娃由大小为从1～m的连续整数的娃娃组成，m的大小在不同的套娃中可能是不同的。

当你重组娃娃的时候，你必须遵守以下规则：

• 你只能把套娃（或者单个的娃娃）放在更大的娃娃里
• 你只能组合相邻的娃娃
• 一旦一个娃娃被套进一组套娃里，它就不能被转移到另一组套娃里或者被长久地分开。仅仅当两组套娃被合并时，它才可以与一组套娃短暂地分离。

你的时间非常值钱，你也想尽可能快地完成合并的操作。这个任务唯一消耗时间的部分是拆开一个娃娃。所以你想尽可能最小化这个操作的次数。

例如，当合并套娃[1 、2、6] 和 [4]时，这个操作的次数是2，因为你要打开大小为6的和4的；合并[1、2、5]和[3、4]时，这个操作次数是3.

请编写一个程序来计算完成任务所需的最小操作次数。

输入

多组数据，每组数据两行.

第一行有一个整数n,为单行套娃的数量(1<=n<=500);

第二行有n个用空格整数分割的整数,表示每个套娃的尺寸，保证尺寸在1～500之间。

输出

对于每组数据，如果能成功合并，输出合并的最小操作次数；

如果无法合并（因为那些热心的孩子可能拿走了几个娃娃），输出“impossible”（不含引号）

样例输入

7

1 2 1 2 4 3 3

7

1 2 3 2 4 1 3

样例输出

impossible

7

做法

代码

#include 
#include 
#include 
using namespace std;
const int maxN = 505;
int N, a[maxN], dp[maxN][maxN], MAX[maxN][maxN], MIN[maxN][maxN], f[maxN][maxN], F[maxN];
bool b[maxN], rep[maxN][maxN], flag;
inline int merge(int a, int b, int c, int d) {
    return f[b][MIN[c][d]] - f[a - 1][MIN[c][d]] + f[d][MIN[a][b]] - f[c - 1][MIN[a][b]];
}
int main() {
    while(scanf("%d", &N) != EOF) {
        flag = 0;
        memset(dp, 0x3f, sizeof(dp));
        memset(MAX, -0x3f, sizeof(MAX));
        memset(MIN, 0x3f, sizeof(MIN));
        memset(f, 0, sizeof(f));
        memset(F, 0x3f, sizeof(F));
        memset(rep, 0, sizeof(rep));
        for(int i = 1; i <= N; i++) 
            scanf("%d", &a[i]), MAX[i][i] = a[i], MIN[i][i] = a[i], dp[i][i] = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(j > i) {
                    MAX[i][j] = max(a[j], MAX[i][j - 1]);
                    MIN[i][j] = min(a[j], MIN[i][j - 1]);
                }
                f[i][j] = f[i - 1][j] + (a[i] > j ? 1 : 0);
            }
        }
        for(int len = 2; len <= N; len++) {
            for(int l = 1; l + len - 1 <= N; l++) {
                int r = l + len - 1;
                for(int k = l; k <= r; k++) {
                    if(!b[a[k]]) b[a[k]] = true;
                    else{flag = true; rep[l][r] = true; break;}                    
                }
                memset(b, 0, sizeof(b));
                if(flag){flag = false; continue;}
                for(int k = l; k < r; k++)
                    dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + merge(l, k, k + 1, r));
            }
        }
        F[0] = 0;
        for(int i = 1; i <= N; i++)
            for(int j = 0; j < i; j++)
                if(MAX[j + 1][i] == i - j && (!rep[j + 1][i]))
                    F[i] = min(F[i], F[j] + dp[j + 1][i]);
        if(F[N] >= 0x3f3f3f3f)     printf("impossible\n");
        else printf("%d\n", F[N]);
    }
    return 0;
}