P16738 [GKS 2019 #F] Flattening

· · 题解

这个问题的反面问题是，在 [1,n] 中选择最多的墙，这些墙都不会被重建，且不满足条件 A_i\neq A_{i+1}(1\leq i<n) 的 i 不超过 k 个。

然后你可以设一个 f_{i,j} 表示前 i 个墙中有 j 个墙不满足条件，能不被重建的最多的墙数，有转移方程：

f_{k,j}+1(1\leq k<i,A_i=A_k)\\ f_{k,j-1}+1(1\leq k<i,A_i\neq A_k)\\ \end{cases}

同时 f_{i,0}=1。

最后答案即为 n-\max\sum_{i=1}^{n}\sum_{j=0}^{k}f_{i,j}，时间复杂度 O(n^2k)，空间复杂度 O(nk)，可以通过。

::::success[解法一代码]

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],f[N][N];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        int n,m,maxn=0;
        scanf("%d%d",&n,&m);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            f[i][0]=1;
            for(int j=0;j<=m;j++)
            {
                for(int k=1;k<i;k++)
                {
                    if(a[i]==a[k])f[i][j]=max(f[i][j],f[k][j]+1);
                    else if(j>=1)f[i][j]=max(f[i][j],f[k][j-1]+1);
                }
                maxn=max(maxn,f[i][j]);
            }
        }
        printf("Case #%d: %d\n",t,n-maxn);
    }
    return 0;
}

::::

尝试优化成 O(nk)。

首先注意到 f_{i,j} 的转移方式仅与 A_i 有关，且动态规划方向从前往后，考虑设 g_{A_i,j} 辅助转移 A_i=A_k 的部分。

对于 A_i\neq A_k 的部分，设 mx_j 和 mxp_j 分别表示 j 的全局最优解以及最优解对应的高度 A_x，nx_j 和 nxp_j 表示 j 的全局次优解以及次优解对应的高度 A_y，注意这里要使 A_x\neq A_y。

五个数组的转移太长了，具体参见代码。

然后注意到问题求解与 A_i 实际大小无关，同时 A_i 大小与 n 不同阶，离散化可将空间优化到 O(nk)。

于是这样时空复杂度均为 O(nk)。

::::success[解法二代码]

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N],f[N],g[N][N];
int mx[N],nx[N],mxp[N],nxp[N];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        int n,m,maxn=0;
        scanf("%d%d",&n,&m);vector<int>Q;
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),Q.emplace_back(a[i]);
        sort(begin(Q),end(Q)),Q.erase(unique(begin(Q),end(Q)),end(Q));
        for(int i=1;i<=n;i++)a[i]=lower_bound(begin(Q),end(Q),a[i])-begin(Q);
        for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)g[a[i]][j]=mx[j]=mxp[j]=nx[j]=nxp[j]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)f[j]=0;f[0]=1;
            for(int j=0;j<=m;j++)
            {
                if(j>=1)
                {
                    if(mxp[j-1]==a[i])f[j]=max(f[j],nx[j-1]+1);
                    else f[j]=max(f[j],mx[j-1]+1);
                }
                f[j]=max(f[j],g[a[i]][j]+1);
                maxn=max(maxn,f[j]);
            }
            for(int j=0;j<=m;j++)
            {
                if(f[j]>mx[j])
                {
                    if(mxp[j]!=a[i])nx[j]=mx[j],nxp[j]=mxp[j];
                    mx[j]=f[j],mxp[j]=a[i];
                }
                else if(f[j]>nx[j]&&mxp[j]!=a[i])nx[j]=f[j],nxp[j]=a[i]; 
                if(f[j]>g[a[i]][j])g[a[i]][j]=f[j];
            }
        }
        printf("Case #%d: %d\n",t,n-maxn);
    }
    return 0;
}

::::