关于本题数学问题的证明

· · 题解

前言：

看到人多人说本题数据很水所以背包能跑过，其实不然。背包能过是存在数学严谨的时间复杂度证明的。本篇题解来解决这个证明问题。

题意：

给你 n 个长度为 m+1 的序列，对于每一个序列而言，满足其编号从 1 到 m+1 的元素单调递增且相邻元素增值为 1，现在将 n 个序列看成一个总集合，从集合中可以任意挑选某种元素再乘若干倍求和表示一个数，问最大的不能表示的自然数。如果都能表示输出 -1。

解释：

第一眼看过，我的题意翻译和原题不同，先说序列元素能否为负数：用原题的背景说，当任一原木材长度小于等于 m 的时候，所有的长度都能表示，这个大家想必都能理解。也就是可以表示 1 的长度，所有的也都可以被表示。所以遇到上述情况输出 -1 即可。还有就是题意存在一种情况是：总有不能表示的木材，输出 -1。现在我要证明的是：这个情况不存在。

证明思路：

欲证原命题，即证存在一个数，满足大于等于它的数都能被表示。先拿出一个序列看：

l-m,l-m+1,l-m+2 \cdots ,l

考虑这个序列能表示哪些数，举个简单的例子：6,7，手模一遍会发现：6,7,12,13,14,18,19,20,21,24,25,26,27,28 等数都能表示，从中发现一些规律：6 和 7 是否可以表示 [\varphi6,\varphi7](\varphi\in N) 区间？可以。证明这里提供一个链接：区间覆盖

有了这个结论后，在推广就得到了一般性结论，也就是上上述序列能表示：[\varphi(l-m),\varphi l](\varphi\in N) 区间。大家能明显发现：这个覆盖区间刚开始不一定是完全连续的本质在于 \varphi l 不一定大于等于 (\varphi+1)(l-m)，求 \varphi 需列出一个方程：

\varphi l\geq(\varphi+1)(l-m) \Rightarrow \varphi\geq \frac{l}{m}-1

也就是：当 \varphi=l/m-1 时，区间 [\varphi(l-m),+\infty) 范围内的数都能表示出来。证毕。 利用上述性质，求出每个序列的上述临界值，再求出 \min(\varphi(l_i-m)) 就可以确定枚举范围了。（换而言之：我们只需要标记上述最小值以下的数就可以了。）

时间复杂度

使用无限背包，枚举木头 O(n)，枚举每个序列 O(m)，枚举背包容量 \frac{(l-m)^2}{m},乘起来就是：n(l-m)^2，所以时间复杂度最大是：100\times3000^2=9\times10^8，忽略常数 10^8 能过，我的代码跑得飞快（离谱），可能是数据把 m 开太大了。

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48); 
        c=getchar();
    }
    return x*f;
}
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
int n,m,l[(int)1e2+(int)1e1],f[(int)9e6+(int)1e1],minx=1e3;
int chu(int x,int y){
    if(x%y==0)return x/y;
    return x/y+1;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i){
        l[i]=read();
        if(l[i]<=m){
            write(-1); return 0;
        }
        minx=min(minx,l[i]-m);
    }
    minx=chu(minx,m)*minx-1; f[0]|=1;
    for(int i=1;i<=n;++i){
        for(int h=l[i]-m;h<=l[i];++h){
            for(int v=h;v<=minx;++v){
                f[v]=max(f[v],f[v-h]);
            }
        }
    }
    for(int i=minx;i>=1;--i){
        if(f[i]==0){
            write(i); return 0;
        }
    }
    write(-1);
    return 0;
}

注：

本篇题解关键在于背包时间复杂度的论述证明，算法固然不好。

AC记录