問題描述
把 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：發現這道題目來源于《演算法競賽進階指南》，原題是 【楊老師的照相排列】，只不過是超級榷訓版，果然多做題才能長見識 😂
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/176145.html
標籤：其他
上一篇：Cinemachine（三）自動選擇/切換最適合的攝像頭（Cinemachine Clear Shot Camera）
下一篇：pyhton實作猜單詞游戲