HDU_5230

http://acm.hdu.edu.cn/showproblem.php?pid=5230

有初始值c，给你1~n的数，输入c+一些数，使得结果在l~r的范围内，输出方案数，注意每种方案中每个数只能使用一次。

可以直接令l和r减去c，便成了分解l~r内的数，求分解方案。

dp[i][j]表示i个数组成j的方案数，根据j最大值推出i最大值，有状态方程dp[i][j] = dp[i][j-i]+dp[i-1][j-i]推出每一个值，最后求出答案即可。

dp[i][j-i]表示相同数量，但每个数都减去一的方案，另外考虑到该方案可以含有1，也就是dp[i-1][j-i]。

另外注意每次要mod一下，于是有了以下代码。

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

#define MOD 998244353

using namespace std;

LL n,c,l,r,dp[][];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        LL ans;

        memset(dp,,sizeof(dp));

        scanf("%d%d%d%d",&n,&c,&l,&r);

        l -= c;

        r -= c;

        if(l)   ans = ;

        else    ans = ;

        dp[][] = ;

        for(int i = ;i*(i+)/ <= r;i++)

        {

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

            {

                dp[i][j] = (dp[i][j-i]+dp[i-][j-i])%MOD;

                if(j >= l)

                {

                    ans = (ans+dp[i][j])%MOD;

                }

            }

        }

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

    }

    return ;

}

然而内存竟然超了，于是改进，使用2个数组轮流交替，得出最终答案。

#include<iostream>

#include<cstdio>

#include<cstring>

#define LL long long

#define MOD 998244353

using namespace std;

LL n,c,l,r,dp[][];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        LL ans;

        memset(dp,,sizeof(dp));

        scanf("%d%d%d%d",&n,&c,&l,&r);

        l -= c;

        r -= c;

        if(l)   ans = ;

        else    ans = ;

        dp[][] = ;

        for(int i = ;i*(i+)/ <= r;i++)

        {

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

            {

                dp[i%][j] = (dp[i%][j-i]+dp[(i+)%][j-i])%MOD;

                if(j >= l)

                {

                    ans = (ans+dp[i%][j])%MOD;

                }

            }

            memset(dp[(i+)%],,sizeof(dp[(i+)%]));

        }

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

    }

    return ;

}

巴特西

HDU_5230_DP

最新文章

热门文章