问题描述
把 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 ++)
{
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：发现这道题目来源于《算法竞赛进阶指南》，原题是 【杨老师的照相排列】，只不过是超级弱化版，果然多做题才能长见识
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
