第十一届蓝桥杯 ——矩阵

问题描述
把 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]
#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 <= 1010; j ++)
        {
            if(i - 1 >= j)                         // 转移前的状态也要合法,即第一行的数量不小于第二行的数量
            	f[i][j] += f[i - 1][j] % 2020;
            if(j)
            	f[i][j] += f[i][j - 1] % 2020;
        }
        
    cout << f[1010][1010] << endl;   
    return 0;
}

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

栏目
728_90 cn stocks