f[i][j]表示走到第i棵树，收集j朵花的方案数，最终答案为f[1][n]+...+f[k][n]。状态转移时，可以枚举在第i棵树收集的花的数量0到s[i]，那么前i-1棵树的数量为max(j-s[i],0)到j，借助前缀和优化即可O(1)求出f[i][j]。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10086001;
int f[5001],n,k,a[5001],ans,sum[5001];//定义，f[i][j]可以优化成f[j]
int main()
{
    cin >> n >> k;
    for(int i = 0;i <= n;i++)sum[i]=1;//开局先赋值
    for(int i = 1;i <= k;i++){
        cin>>a[i];
        for(int j = 0;j <= a[i];j++){
            f[j] = sum[j];//状态转移要分类讨论
        }
        for(int j = a[i]+1;j <= n;j++){
            f[j] = (sum[j]-sum[j-a[i]-1]+MOD)%MOD;//这个部分会有点难，需要慢慢消化
        }
        ans = (ans+f[n])%MOD;
        sum[0] = f[0];
        for(int j = 1;j <= n;j++){
            sum[j] = (sum[j-1]+f[j])%MOD;//这里前缀和优化
        }
    }
    if(ans == 0){//判断这里是否有收集到n朵樱花
        cout << "impossible";
        return 0;
    }
    cout << ans;
    return 0;
}//完美收尾

点个赞吧，求求了。

f[i][j]表示走到第i棵树，收集j朵花的方案数，最终答案为f[1][n]+...+f[k][n]。状态转移时，可以枚举在第i棵树收集的花的数量0到s[i]，那么前i-1棵树的数量为max(j-s[i],0)到j，借助前缀和优化即可O(1)求出f[i][j]。

for (int i = 0; i <= n; i++)
    sum[i] = 1;
for (int i = 1; i <= k; i++) {
    cin >> s[i];
    for (int j = 0; j <= s[i]; j++) {
        f[j] = sum[j];
    }
    for (int j = s[i] + 1; j <= n; j++) {
        f[j] = (sum[j] - sum[j - s[i] - 1] + MOD) % MOD;
    }
    ans = (ans + f[n]) % MOD;
    sum[0] = f[0];
    for (int j = 1; j <= n; j++) {
        sum[j] = (sum[j - 1] + f[j]) % MOD;
    }
}
if (ans == 0)
    cout << "impossible";
else 
    cout << ans;

题解： #include<bits/stdc++.h> using namespace std; int n,k,MOD=10086001; int s[5050],sum[5050],f[5050]; int ans; int main() { cin>>n>>k; for (int i = 0; i <= n; i++) sum[i] = 1; for (int i = 1; i <= k; i++) { cin >> s[i]; for (int j = 0; j <= s[i]; j++) { f[j] = sum[j]; } for (int j = s[i] + 1; j <= n; j++) { f[j] = (sum[j] - sum[j - s[i] - 1] + MOD) % MOD; } ans = (ans + f[n]) % MOD; sum[0] = f[0]; for (int j = 1; j <= n; j++) { sum[j] = (sum[j - 1] + f[j]) % MOD; } } if (ans == 0) cout << "impossible"; else cout << ans; return 0; }#hetao845776

#include<bits/stdc++.h>
using namespace std;
int n,k,MOD=10086001;
int s[5050],sum[5050],f[5050];
int ans;
int main()
{
    cin>>n>>k;
    for (int i = 0; i <= n; i++)
    sum[i] = 1;
    for (int i = 1; i <= k; i++)
    {
        cin >> s[i];
        for (int j = 0; j <= s[i]; j++)
        {
            f[j] = sum[j];
        } 
        for (int j = s[i] + 1; j <= n; j++)
        {
            f[j] = (sum[j] - sum[j - s[i] - 1] + MOD) % MOD;
        } 
        ans = (ans + f[n]) % MOD;
        sum[0] = f[0];
        for (int j = 1; j <= n; j++)
        {
            sum[j] = (sum[j - 1] + f[j]) % MOD;
        }
    }
    if (ans == 0)
        cout << "impossible";
    else
        cout << ans;
    return 0;
}

#include<bits/stdc++.h> using namespace std; int n,k,MOD=10086001; int s[5050],sum[5050],f[5050]; int ans; int main() { cin>>n>>k; for (int i = 0; i <= n; i++) sum[i] = 1; for (int i = 1; i <= k; i++) { cin >> s[i]; for (int j = 0; j <= s[i]; j++) { f[j] = sum[j]; } for (int j = s[i] + 1; j <= n; j++) { f[j] = (sum[j] - sum[j - s[i] - 1] + MOD) % MOD; } ans = (ans + f[n]) % MOD; sum[0] = f[0]; for (int j = 1; j <= n; j++) { sum[j] = (sum[j - 1] + f[j]) % MOD; } } if (ans == 0) cout << "impossible"; else cout << ans; return 0; }