算法_dp

2023牛客寒假算法基础集训营1 B题 四维dp+前缀和处理

题目描述

众所周知，2022年是四年一度的世界杯年，那么当然要整点足球题。本题需要你模拟一支队伍的一赛季联赛征程。

联赛的规则是，踢若干场比赛。每赢一场（进球数大于对方）比赛得3分，每输一场比赛（进球数小于对方）得0分，每次平局（进球数等于对方）得1分。
已知在接下来一个赛季的n轮比赛里，某队一共进了x个球，而某队的n个对手在和某队的比赛中一共进了y个球。求这n轮有多少种不同的比赛结果使得本赛季某队获得至m分。
之中对于两种比赛结果，若n轮比赛中至少有一场的比分不一样，就认为两种比赛结果不同。

输入描述:

输入仅包含一行四个整数
n,m,x,y(1≤n≤40,0≤m≤120,0≤x,y≤100)，之间用空格分隔开，含义如题目所述。

输出描述:

输出一个数字，为答案对998244353取模的结果。

#include <iostream>
using namespace std;

int n, m, x, y;
const int mod = 998244353;
const int N = 41 * 3;

int dp[125][101][101];
int line[125][101][101], down[125][101][101], up[125][101][101];

/*
思路：
    dp[i][j][s][t]表示前i场比赛中总得分为j，a队得分s，b队得分t的种类数。
    若输了  +=dp[i-1][j][s-k][t-l] (k=0-s,l=0-t,k<l)    //左侧45°梯形
    若赢了  +=dp[i-1][j-3][s-k][t-l] (k=0-s,l=0-t，k>l) //youce
    平      +=dp[i-1][j-3][s-k][t-l] (k=0-s,l=0-t，k=l) //对角线

代码;
    现预处理出down,up,line的数组值，在依次枚举，因队dp[i][j][s][t]仅用到dp[i-1]可省去一维，对上一维的数据处理其

    1、若球队一直赢时，得分最高位n*3,而不是题目中的m，m是最小计算种类数的值
    2、down，line，up三个数组初始化时，down表示的是左侧角等于45的左侧梯形的所有dp[i-1][j][s][t]的和，up也是如此
    3、dp数组迭代时，若球队本场赢了，dp[j][s][t]+=down[j][s][t-1]，而不是用up数组，down数组表示球队赢得多。
*/

int main()
{
    cin >> n >> m >> x >> y;
    dp[0][0][0] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= n * 3; j++)
        {
            for (int s = 0; s <= x; s++)
                down[j][s][0] = line[j][s][0] = dp[j][s][0];
            for (int t = 0; t <= y; t++)
                up[j][0][t] = line[j][0][t] = dp[j][0][t];

            for (int u = 1; u <= x; u++)
            {
                for (int v = 1; v <= y; v++)
                {
                    line[j][u][v] = (line[j][u - 1][v - 1] + dp[j][u][v]) % mod;
                }
            }
            for (int u = 0; u <= x; u++)
            {
                for (int v = 0; v <= y; v++)
                {
                    if (v)
                        down[j][u][v] = (down[j][u][v - 1] + line[j][u][v]) % mod;
                    if (u)
                        up[j][u][v] = (up[j][u - 1][v] + line[j][u][v]) % mod;
                }
            }
        }

        for (int j = 0; j <= n * 3; j++)
        {
            for (int s = 0; s <= x; s++)
            {
                for (int t = 0; t <= y; t++)
                {
                    dp[j][s][t] = 0;
                    if (j >= 0)
                    {
                        if (t)
                            dp[j][s][t] += down[j][s][t - 1];
                        dp[j][s][t] %= mod;
                    }
                   
                    if (j >= 3)
                    {
                        if (s)
                            dp[j][s][t] += up[j - 3][s - 1][t];
                        dp[j][s][t] %= mod;
                    }
                       
                    if (j >= 1)
                        dp[j][s][t] += line[j - 1][s][t];
                    dp[j][s][t] %= mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i = m; i <= n*3; i++)
    {
        ans += dp[i][x][y];
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}