题目内容

P2933

大意:给定一个集合,求满足条件的最小子集。

解题思路

观察这个问题,发现选择的数越小,误差的值越大。

然后我们就发现了这题貌似具有最优子结构性质:考虑前 i 个元素中选了 j 个(包括第 i 个),考虑的问题就变成了继续选元素的问题,可以用 dp 解决。

f_{i,j} 表示前 i 个元素中选了 j 个(包括第 i 个元素)时可以获得的最小误差,这样子状态就定义好了。转移的时候使用刷表法往后推进,通过提前预处理就可以很方便的处理误差。

正确性:因为这样进行转移的时候,元素是从前往后进行选择的,而两两被选择元素中间元素的误差是确定的。当我们从第 i 个元素向后转移的时候,前面的误差值是已经计算好了,无需再进行考虑。同时为了方便,构造了一个第 n+1 个元素,这样的话方便最后进行统计答案。

一开始时,为了在转移时能够很快的获得两个元素之间的误差值,我们可以令 g_{i,j} 表示选择了第 i 和第 j 个元素时,中间其余元素贡献的误差。 g_{0,i} 表示只选择第 i 个元素时前面所有元素产生的误差,g_{i,n+1} 表示只选择第 i 个元素时后面所有元素产生的误差。

i+1 开始向后枚举 k 转移方程为 f_{k,j+1}=\min(f_{k,j+1},f_{i,j}+g_{i,k})

预处理和转移时复杂度都为 O(n^3),最终复杂度 O(n^3)

#include <cstdio>
#include <cctype>
#include <cstring>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int abs(int x)
{
    return x<0?-x:x;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

const int maxn=105;
int n,e,m[maxn];
int f[maxn][maxn],g[maxn][maxn];

int main()
{
    n=read(),e=read();
    for(int i=1;i<=n;i++)
        m[i]=read();
    //预处理
    for(int i=0;i<=n+1;i++)
        for(int j=i+1;j<=n+1;j++)
            for(int k=i+1;k<=j-1;k++)
                if(i==0)
                    g[i][j]+=abs(2*(m[j]-m[k]));
                else if(j==n+1)
                    g[i][j]+=abs(2*(m[i]-m[k]));
                else
                    g[i][j]+=abs(2*m[k]-m[i]-m[j]);
    memset(f,0x3f,sizeof f);//先赋极大值
    f[0][0]=0;//初始条件
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            if(f[i][j]<=e)//转移有意义的前提是此时的误差仍小于e,不然转一下去也是非法的
                for(int k=i+1;k<=n+1;k++)
                    f[k][j+1]=min(f[k][j+1],f[i][j]+g[i][k]);
    for(int i=2;i<=n+1;i++)//统计答案,因为我们认为第 n+1 个元素被选择了,所以要多考虑
        if(f[n+1][i]<=e)
        {
            printf("%d %d\n",i-1,f[n+1][i]);//找到最小的子集大小就可以直接结束程序了
            return 0;
        }

}
最后修改日期:2020年8月30日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。