这题最难的点在于突破口。

考虑如果放不进任何一根木棍，就代表未使用的最短的木棍也放不进去，可以枚举这根木棍。

对长度有限制先排序。假设当前枚举到第 $i$ 根，如果放不进去需要满足什么式子？设当前已经放进去的木棍长度和板子长度分别为 $l$ 和 $m$，间隔个数为 $p$，有 $l+p \times a_i>m$，因为间隔的长度只能小于 $a_i$，所以如果间隔长度都为 $a_i$ 必须比 $m$ 大而不能相等。

上式中 $l$ 和 $p$ 不能确定，发现 $p$ 就是用了的木棍数量 $+1$。因为 $1$ 到 $i-1$的木棍必须选，这部分可以直接求和，而 $i+1$ 到 $n$ 的木棍可以选也可以不选。又因为还需要记录数量，发现本质是一个 01 背包。

如果放的长度比板子还大，显然也不行，所以背包最大体积开到 $1000$。同时在求答案时也要注意判断 $l<=m$。

每一次直接找当前能凑出的长度，判断是否满足上面两个条件如果有就更新答案。

代码中直接用了 bitset，好用又快。

#include<bits/stdc++.h> 
using namespace std; 
int m,n,a[35],ans; 
bitset<1005>dp[35]; 
int main()
{     
    cin>>m>>n;
    ans=n;     
    for(int i=1;i<=n;i++)    
        cin>>a[i];     
    sort(a+1,a+n+1);     
    int s=0;     
    for(int i=0;i<=n;i++)
    {         
        s+=a[i];         
        for(int k=0;k<=n;k++)
            dp[k].reset();         
        dp[0].set(0);         
        for(int j=i+2;j<=n;j++)
            for(int k=(j-1)-(i+1);k>=0;k--)
                dp[k+1]|=dp[k]<<a[j];         
        for(int k=0;k<=n;k++)
            for(int p=dp[k]._Find_first();p<=m;p=dp[k]._Find_next(p))             
                if(m>=p+s && m-p-s<a[i+1]*(k+i+1))ans=min(ans,i+k);     
    }     
    printf("%d",ans); 
    return 0;
}

分析复杂度是 $O(\frac{n^3+n^2m}{w})$。

但是观察上面的代码，每次枚举到新的 $i$ 时都重新求了一遍背包，太过笨重。原因是每次从背包中删除一个元素。能不能每次不是删除而是添加元素呢？发现如果倒序枚举 $i$ 就可以了。

所以又有这一版代码（不是我写的，直接粘的）：

#include <bits/stdc++.h>
#include <bits/extc++.h>

using u32 = int;

u32 L, n, a[31], s[31], ans;
std::bitset<1001> dp[31];

signed main(void) {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cin >> L >> n;
    for (u32 i{ 1 }; i <= n; i++) {
        std::cin >> a[i];
    }
    std::sort(a + 1, a + n + 1);
    for (u32 i{ 1 }; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    dp[0].set(0);
    ans = n;
    for (u32 i{ n }; i; i--) {
        if (s[i - 1] <= L)
            for (u32 j{ 0 }; j <= n - i; j++) {
                int pos = L - (i + j) * a[i] - s[i - 1] + 1;
                for (u32 l{ 0 }; l <= L - s[i - 1]; l++) {
                    if (dp[j][l] && l >= pos) {
                        ans = std::min(ans, i - 1 + j);
                    }
                }
            }
        for (u32 j{ n - i + 1 }; j; j--) {
            dp[j] |= dp[j - 1] << a[i];
        }
    }
    std::cout << ans;
}

复杂度是 $O(n^2m)$。

这份代码显然差在不需要遍历所有长度，但其实也没必要像第一份代码一样。因为只关心存在性，所以先求出符合第一个式子最小的 $l$，减去必须选的后找到能凑出的最小的比 $l$ 大的长度就行，因为第二个式子显然 $l$ 越小越有可能符合。

#include<bits/stdc++.h>
using namespace std;
int a[35],s[35];
bitset<1005>f[35];
int main()
{
    int m,n;
    cin>>m>>n;
    int ans=n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];
    f[0].set(0);
    for(int i=n;i>=1;i--)
    {
        if(s[i-1]<=m)//(这一行其实有没有都可以，如果大于r一定小于0，m-s[i-1]又小于0，一定不会合法)
        {
            for(int j=0;j<=n-i;j++)
            {
                int r=m-s[i-1]-(i+j)*a[i];
                if(r<0)    
                {
                    if(f[j]._Find_first()<=m-s[i-1])
                        ans=min(ans,i+j-1);
                }
                else
                {
                    if(f[j]._Find_next(r)<=m-s[i-1])
                        ans=min(ans,i+j-1);
                }
            }
        }
        for(int j=n-i+1;j;j--)
            f[j]|=f[j-1]<<a[i]; 
    }
    cout<<ans;
    return 0;
}

复杂度是 $O(\frac{n^2m}{w})$。

总结一下，这题从思路到优化上都非常精妙，应该能评到上位蓝。