题解：P17205 「DLESS-6」Tnemerced Tnemercni

· · 题解

一些补充。

原始问题是求 \min \sum k|x_S|+|v_i|，其被 \sum x_{i\in S}+v_i=a_i 所约束。

求其拉格朗日函数，得到：

L(x,v,y)=\sum k|x_S|+\sum |v_i| +\sum y_i\big (a_i-\sum x_{i\in S}-v_i\big )

如何理解呢？可以将 y_i 看作惩罚因子。对于固定的 (x,v)，若不满足条件，此函数的最大值将会到 +\infty。因此，这个固定 (x,v) 的函数的最大值的最小值就是所求值。

对于线性规划问题，若固定 y，这个函数的最小值的最大值 m' 一定会等于所求值 m。即对于线性规划，只要原问题可行且有界（即满足 Slater 条件），强对偶定理必然成立。由于实力不足无法给出简要证明。

为了进一步求解，作变形如下：

L(x,v,y)=\sum \big(k|x_S|-x_S\sum y_{i\in S}\big)+\big(\sum |v_i|-v_iy_i\big) +\sum y_ia_i

发现这个函数仍然是线性规划问题的形式（但是是关于 y 的），所以考虑给他变回去。注意现在变成了求最大值的最小值，与原问题对偶，所以优化目标变成了求最大值。

但是，注意到 |y_i|>1 时仅凭 \sum |v_i| 无法对第二项给予足够的惩罚，所以要手动补上 |y_i|\le 1。第一项也要类似处理。

可得其对偶问题即：

\max y_ia_i,\\\text{s.t.} \Big|\sum y_{i\in S}\Big|\le k,|y_i|\le 1

直接 DP 可能会退化到 O(nk^2)，寄，因为你需要考虑两个界。

需要利用自身的性质，考虑到无需照顾 -l_i 过多的情况，因为本来就不优。所以条件变为 \sum y_{i\in S}\le k。

这样就可以 O(nk) 了，设 f_{i,j} 表示 i 的后缀和最大为 j 的答案，滚动一下就可以了。

:::info[Code]

#include "common.h"
const int N=2e5+1,K=2001;
const ll INF=1e18;
int n,k;
int l[N],r[N];
ll f[2][K],ans;
int main()
{
    read(n);read(k);
    for(int i=1;i<=n;i++)read(l[i]),read(r[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=k;j++)
        for(int cur=-1;cur<=1;cur++)
        if(j+cur<=k)
        {
            int g=max(0,j+cur);
            f[1][g]=max(f[1][g],f[0][j]+max(l[i]*cur,r[i]*cur));
            if(i==n)ans=max(ans,f[1][g]);
        }
        for(int j=0;j<=k;j++)f[0][j]=f[1][j],f[1][j]=-INF;
    }
    writel(ans,'\n');
    return 0;
}

:::