LOJ 6089 小Y的背包计数问题 —— 前缀和优化DP

题目：https://loj.ac/problem/6089

对于 i <= √n ，设 f[i][j] 表示前 i 种，体积为 j 的方案数，那么 f[i][j] = ∑(1 <= k <= i ) f[i-1][j - k*i]

可以用前缀和优化，因为第 i 次只会用到间隔为 i 的和；

对于 i > √n ，最多选 √n 个，所以设 g[i][j] 表示用 i 个，体积为 j 的方案数；

每种方案如果排一个序，就是一个最小值为 √n + 1 的不降序列，所以算出不降序列的个数也就知道了方案数；

要得到一个长度为 i 的这样的序列，可以通过两种操作从 i - 1 的序列得到，即新加一个 √n + 1，或整体 + 1；

二者合并起来就是答案；

调了一下午，就是因为 f[] 数组开成 √n 大小了？为什么没有段错误提示？？

会写前缀和优化DP啦...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long ll;

int const maxn=1e5+,maxm=,mod=;

int n,f[maxn],g[maxm][maxn],s[maxn],t[maxn],ans;

int main()

{

    scanf("%d",&n);  int sq=sqrt(n);

    f[]=;

    for(int i=;i<=sq;i++)

    {

        for(int j=;j<=n;j++)s[j]=(f[j]+(j>=i?s[j-i]:))%mod;

        for(int j=;j<=n;j++)

        {

            f[j]=s[j];

            if(j>=(i+)*i)f[j]=(f[j]-s[j-(i+)*i]+mod)%mod;

        }

    }

    g[][]=;

    ans=f[n];//

    for(int i=;i<=sq;i++)

        for(int j=i*(sq+);j<=n;j++)//i*

        {

            g[i][j]=(g[i-][j-sq-]+g[i][j-i])%mod;

            ans=(ans+(ll)g[i][j]*f[n-j]%mod)%mod;

        }

    printf("%d\n",ans);

    return ;

}