第十一届蓝桥杯 ——矩阵

112 阅读 0 评论 74 点赞

我是靠谱客的博主整齐河马，这篇文章主要介绍第十一届蓝桥杯 ——矩阵，现在分享给大家，希望可以做个参考。

问题描述
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。

要求同一行中右边的比左边大，同一列中下边的比上边的大。一共有多少种方案？

答案很大，你只需要给出方案数除以 2020 的余数即可。

答案提交
这是一道结果填空题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

答案：1340

题解
动态规划：

f[i][j]：所有第一行有 i 个数字，第二行有 j 个数字的方案数量；

决策：

将当前数放在第一行：f[i][j] += f[i - 1][j]；
将当前数放在第二行：f[i][j] += f[i][j - 1]；

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

int f[1020][1020];

int main()
{
    f[0][0] = 1;                                   // 两行一个数字都不放，也是一种方案
    for (int i = 0; i <= 1010; i ++)
        for (int j = 0; j <= i; j ++)
        {
            if(i - 1 >= j)                         // 转移前的状态也要合法，即第一行的数量不小于第二行的数量
            	f[i][j] += f[i - 1][j] % 2020;
            if(j - 1 >= 0)
            	f[i][j] += f[i][j - 1] % 2020;
        }
        
    cout << f[1010][1010] << endl;   
    return 0;
}