[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka

紫书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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

此站点使用 Akismet 来减少垃圾评论。了解我们如何处理您的评论数据