题解：AT_cf16_exhibition_final_f Intervals

· · 题解

AT_cf16_exhibition_final_f Intervals 题解

博客园，博客园，我们马上就到：AT_cf16_exhibition_final_f Intervals 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

贪心，DP。

分析

可以证明有一个区间一定不动，分奇偶即可。

接下来很直观地可以感受到要把区间分到两边，且短的放在离不动区间近的会更优，所以我们降序排序。

进一步地，把区间对半分开放到左右也会让答案不劣，这就与初中的绝对值问题类似。

我们可以列出答案的表达式：设左边选到了第 i 个，右边选到了第 j 个。

那么可以考虑拆贡献，这里要分为奇偶两种情况：

  1. 那么较为简单，设 $m=\lfloor \frac{n}{2} \rfloor$，左边和右边各会选 $m$ 个区间。贡献为： $$ \sum_{i}[(i-1)(R_{1,i}-L_{1,i}) + R_{1,i}] + \sum_{j}[(j-1)(R_{1,j}-L_{1,j}) - L_{1,j}] + m(R_x-L_x) \\ $$
  2. 考虑不动的区间随意取中间两个其中一个即可。设 $m=\lfloor \frac{n}{2} \rfloor$，左边取 $m-1$ 个，右边取 $m$ 个。贡献为： $$ \sum_{i}[(i-1)(R_{1,i}-L_{1,i}) + R_{1,i}] + \sum_{j}[(j-1)(R_{1,j}-L_{1,j}) - L_{1,j}] + mR_x-(m-1)L_x \\ $$

那么 DP 状态就是 f_{l,r,0/1} 表示左边选了 l 个，右边选了 r 个，0/1 表示是否已经选取了不动的区间，如果空间不够考虑滚动数组优化。

剩下的转移从上面即可推出，复杂度 O(n^2)。

代码

constexpr int N(5e3+10);

int n,L,R;
struct node {
    int l,r;
    node(int l=0,int r=0):l(l),r(r) {}

    void Input() { scanf("%d%d",&l,&r),l=-l; }

    int len() { return r-l; }

    friend bool operator <(node a,node b) { return a.len()>b.len(); }
} a[N];
ll f[N>>1][2],_f[N>>1][2];

signed main() {
    /*DE("Input");*/
    scanf("%d",&n),L=(n-1)>>1,R=n>>1;
    FOR(i,1,n)a[i].Input();
    sort(a+1,a+n+1);
    /*DE("DP");*/
    FOR(l,0,(n+1)>>1)f[l][0]=f[l][1]=LINF;
    f[0][0]=0;
    FOR(i,1,n) {
        FOR(l,0,min(i,L))_f[l][0]=_f[l][1]=LINF;
        FOR(l,0,min(i-1,L)) {
            int r((i-1)-l);
            if(l<L)tomin(_f[l+1][0],f[l][0]+(ll)l*a[i].len()+a[i].r);
            if(r<R)tomin(_f[l][0],f[l][0]+(ll)r*a[i].len()-a[i].l);
            tomin(_f[l][1],f[l][0]+(ll)R*a[i].r-(ll)L*a[i].l);
        }
        FOR(l,0,min(i-2,L)) {
            int r((i-1)-l-1);
            if(l<L)tomin(_f[l+1][1],f[l][1]+(ll)l*a[i].len()+a[i].r);
            if(r<R)tomin(_f[l][1],f[l][1]+(ll)r*a[i].len()-a[i].l);
        }
        swap(f,_f);
    }
    /*DE("Output");*/
    printf("%lld\n",f[L][1]);
    return 0;
}