P10197 题解

· · 题解

Problem Link

题目大意

给定长度为 n 的序列 a_1\sim a_n，给定 k 个位置不能交换，其他位置上的元素可以任意交换，最小化 \sum\limits_{i=1}^{n-1}\max(a_i,a_{i+1})。

数据范围：n\le 300,k\le 6。

思路分析

从 k=0 的情况开始，注意到 \max(a_i,a_{i+1})=\dfrac 12(a_i+a_{i+1}+|a_i-a_{i+1}|)，因此我们只要最小化 \sum |a_i-a_{i+1}|，升序或降序排列即可。

回到一般的问题，我们设 a_0=a_{n+1}=\infty 且这两个位置不能交换，那么整个序列就被不能交换的点分成若干个区间 (l_i,r_i)，我们只要把可以交换的元素填入这些区间即可。

假设我们在区间 (l_i,r_i) 中填的元素是 S，根据刚才的结论，显然 S 升序排列或降序排列最优，如果 a_{l_i}<a_{r_i} 那么升序排列，否则降序排列。

设 S 中元素的最大最小值分别为 \max_i,\min_i，那么这一段区间的贡献就是 |a_{l_i}-\min_i|+|a_{r_i}-\max_i|+\max_i-\min_i。

注意到关于 \max_i 的贡献为 |a_{r_i}-\max_i|+\max_i 随着 \max_i 变小递减，关于 \min_i 的贡献 |a_{l_i}-\min_i|-\min_i 随着 \min_i 变大递减。

因此可以通过调整法证明每个区间内的值域区间 [\min_i,\max_i] 要么相离要么包含，否则可以把相交区间切成两部分，使得 \max_i 变小 \min_j 变大。

那么就可以考虑在值域上 dp，设可以交换的元素排序后是 w_1\sim w_m，那么设 f_{l,r,S} 表示考虑 S 中的区间用 w_l\sim w_r 中的元素填满的最小代价。

根据代价函数的性质进一步分析，我们发现：对于两个值域区间 [\min_i,\max_i]\subseteq[\min_j,\max_j]，[\min_i,\max_i] 内部不可能有元素在 j 中，否则交换该元素和 \min_i 即可让 \min_i 变大。

设 S 中的区间大小总和为 siz_S，那么我们只要在 r-l+1=siz_S 时考虑向 S 中插入一个区间，否则直接从 \min(f_{l,r-1,S},f_{l+1,r,S})。

考虑插入区间的形式：

时间复杂度 \mathcal O(n^2(3^k+k2^k))。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int V=1e6+5;
int a[305],L[10],R[10],len[10],sz[1<<7],w[305],id[10],f[305][305][1<<7];
void chkmin(int &x,int y) { x=x<y?x:y; }
signed main() {
    int N,M,n=0,m=0,ans=0;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i) scanf("%d",&a[i]),ans+=2*a[i];
    for(int i=1;i<=M;++i) scanf("%d",&id[i]);
    a[0]=a[N+1]=V,id[0]=0,id[M+1]=N+1,ans+=2*V;
    for(int i=0;i<=M;++i) {
        if(id[i+1]-id[i]==1) ans+=abs(a[id[i]]-a[id[i+1]]);
        else {
            L[m]=id[i],R[m]=id[i+1],len[m]=R[m]-L[m]-1;
            for(int j=L[m]+1;j<=R[m]-1;++j) w[++n]=a[j];
            if(a[L[m]]>a[R[m]]) swap(L[m],R[m]); ++m;
        }
    }
    sort(w+1,w+n+1);
    for(int s=0;s<(1<<m);++s) for(int i=0;i<m;++i) if(s>>i&1) sz[s]+=len[i];
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=n;++i) f[i+1][i][0]=0;
    for(int d=1;d<=n;++d) for(int l=1,r=d;r<=n;++l,++r) for(int s=0;s<(1<<m);++s) if(sz[s]<=d) {
        f[l][r][s]=min(f[l][r-1][s],f[l+1][r][s]);
        for(int t=(s-1)&s;t;t=(t-1)&s) {
            chkmin(f[l][r][s],f[l][l+sz[t]-1][t]+f[l+sz[t]][r][s^t]);
        }
        if(sz[s]<d) continue;
        for(int j=0;j<m;++j) if(s>>j&1) {
            int z=abs(a[L[j]]-w[l])+abs(a[R[j]]-w[r])+w[r]-w[l];
            if(len[j]==1&&d==1) {
                chkmin(f[l][r][s],z);
            } else if(len[j]>1) {
                chkmin(f[l][r][s],f[l+1][r-1][s^(1<<j)]+z);
            }
        }
    }
    printf("%d\n",(ans+f[1][n][(1<<m)-1])/2-2*V);
    return 0;
}