第十一届蓝桥杯 ——矩阵

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

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

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

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

答案：1340

题解
动态规划：

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

决策：

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

#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;
}

ps：发现这道题目来源于《算法竞赛进阶指南》，原题是 【杨老师的照相排列】，只不过是超级弱化版，果然多做题才能长见识 ????

蓝桥杯C/C++组省赛历年题

最后

以上就是整齐河马为你收集整理的第十一届蓝桥杯 ——矩阵的全部内容，希望文章能够帮你解决第十一届蓝桥杯 ——矩阵所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。