紫书DP课后题最后一题了，也算是把这一部分做完了吧。
这个题，在uva上的数据太水了，导致很多网上的题解代码是错误的。在gym10128H这里会wa。这些题解大多是用一个简单的贪心策略处理分段，然后用区间dp处理分出来的段落。但是实际上分段也需要用一个dp，比如数据 1 2 4 3 1 2，用简单的贪心分段就会把4 3分到前面那一段，这样的出来结果是5（当把1 2 放进4 3里的时候4和3都要打开），但是如果把4 3分到后面的1 2里答案是4，是更优的解。
先讲简单的部分：分好段之后的区间dp。这个就是普通的区间dp $$dp(l,r)=min(dp(l,i)+dp(i+1,r)+cost(l,i,i+1,r)),i\in[l,r)$$其中 \[dp(l,r)\]表示
[l,r]之间的套娃组装成1个所需要的最小花费,
\[cost(l,i,i+1,r)\]表示把这两段合并起来的花费。设mi(l,r)为\[[l,r]\]之间的最小值，则不难发现cost就是
\[[l,r]\]中的元素数量-（除了\[max(mi(l,i),mi(i+1,r))\]所在的一段的另外一段中的小于\[max(mi(l,i),mi(i+1,r))\]的数的个数） （可能说起来有点绕但是画几组样例很好理解）。这样可以递推预处理出来所有的mi(i,j)，然后每次dp的时候计算cost。（爆炸的复杂度
然后再说这个题比较难的也是有意思的部分：如何分段。这个让我没想到的骚操作是我一直感觉应该先分段再dp，这里竟然是先区间dp再分段。想了想才明白，区间dp其实只需要保证dp的对象区间满足他是从1开始的连续的一段数字（比如 1 3 2 4就是，而1 4 2不是）就可以得出正确的结果，那么我们可以先把所有的满足这种条件的段的区间dp值都处理出来，这里最精妙的一点就是如何判断这一段区间是满足这个条件的，其实只要满足两个条件（选这两个条件是因为比较好处理，这里如何预处理出来区间中数字的唯一性我也是从dalao的题解中学到的，细节看代码中is_unique数组的计算）
①区间的最大值等于区间的长度
②区间里面的元素都是独一无二的
这样的话还看上面的1 2 4 3 1 2这组数据，就会有两个\[ dp(l,r) \]覆盖到4 3这一段，其值都已经被正确的计算出来。这时候我们可以再通过一个线性dp来决定最优解\[f[i]=min(f[j]+dp[j+1][i]),j\in[0,i),i\in[1,n] \]这样就可以完整的解决这个题目了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500 + 15;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxnode = 1e6 + 5;
typedef long long LL;
typedef unsigned long long ULL;
int n,ori[maxn];
int pre[maxn][maxn][2],dp[maxn][maxn],fdp[maxn];;
int mi[505][505],mx[505][505];
int tmp[maxn];
int dps(int l,int r)
{
if(l>=r)
return 0;
else
{
if(dp[l][r]!=INF)
return dp[l][r];
int best=INF,tt,nu=0;
for(int i=l;i<r;i++)
{
nu=0;
if(mi[l][i]<mi[i+1][r])
{
tt=mi[i+1][r];
for(int k=l;k<=i;k++)
nu+=(ori[k]<tt);
}
else
{
tt=mi[l][i];
for(int k=i+1;k<=r;k++)
nu+=(ori[k]<tt);
}
best=min(best,r-l+1-(nu)+dps(l,i)+dps(i+1,r));
}
return dp[l][r]=best;
}
}
int bf[maxn],cur[maxn],is_unique[maxn][maxn];
void precal(int n)
{
memset(dp,INF,sizeof(dp));
memset(mx,0,sizeof(mx));
memset(mi,INF,sizeof(mi));
memset(cur,0,sizeof(cur));
memset(fdp,INF,sizeof(fdp));
for(int i=1;i<=n;i++)
{
bf[i]=cur[ori[i]];
cur[ori[i]]=i;
mx[i][i]=ori[i],mi[i][i]=ori[i],is_unique[i][i]=1,dp[i][i]=0;
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
mx[i][j]=max(mx[i][j-1],ori[j]);
mi[i][j]=min(mi[i][j-1],ori[j]);
is_unique[i][j]=(is_unique[i][j-1]&&bf[j]<i);
}
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&ori[i]);
precal(n);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
if(j-i+1==mx[i][j]&&is_unique[i][j])
dps(i,j);
fdp[0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<i;j++)
if(i-j==mx[j+1][i]&&is_unique[j+1][i])
fdp[i]=min(fdp[i],fdp[j]+dp[j+1][i]);
if(fdp[n]==INF)
puts("impossible");
else
{
printf("%d\n",fdp[n]);
}
}
return 0;
}