题解：P9102 [PA 2020] Cukierki

Storm_Lightning · 2025-04-13 11:21:22 · 题解

大致思路

根据算法标签，可知这题是一道动态规划。

首先定义 dp[i][j] 表示前 i 个数能够表示 [1，j] 这个范围中的所有数字。

由题显然可得：

很显然应为均为 i-1 ，所以这一维直接滚掉。

我们把数组从小到大排序，根据贪心可知，在 a_i<a_j 时，如果加上 a_i 时，就大于总数，则 a_j 就不用说了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3,mod=1e9+7;
int n,a[maxn+5],f[maxn+5],ans;
signed main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
    }
    sort(a+1,a+n+1);
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=maxn;j>=a[i]-1;j--)
        {
            int now=min(j+a[i],maxn);
            f[now]=(f[now]+f[j])%mod;
        }
    }
    for(int i=1;i<=maxn;i++)
    {
        ans=(ans+f[i])%mod;
    }
    printf("%d",ans);
    return 0;
}