5753 | 2023. 09. 16 13:09:45 | Ablablabla | Járda-L (40) | cpp17 | Elfogadva 40/40 | 3ms | 4356 KiB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dp;
int megold(int teljes, int fel){
if(teljes < 0){
return 0;
} else if(teljes == 0 && fel == 0){
return 1;
}
if(dp[teljes][fel] != -1){
return dp[teljes][fel];
}
int vissza = 0;
if(fel == 2){
vissza += megold(teljes, 0); // kettes fektetve
} else if(fel == 1){
vissza += megold(teljes - 1, 1); // kettes fektetve
vissza += megold(teljes - 1, 0); // L
} else if(fel == 0){
vissza += megold(teljes - 2, 2); // kettes fektetve
vissza += megold(teljes - 1, 0); // kettes allitva
vissza += megold(teljes - 2, 1) * 2; // L
}
//cout << teljes << " " << fel << " : " << vissza << "\n";
return dp[teljes][fel] = vissza;
}
int main()
{
int n;
cin >> n;
dp.assign(n + 1, vector<int>(3, -1));
cout << megold(n, 0) << "\n";
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1812 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2056 KiB | |||
3 | Elfogadva | 2/2 | 2ms | 2276 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2436 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2684 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2776 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2904 KiB | |||
8 | Elfogadva | 3/3 | 3ms | 3120 KiB | |||
9 | Elfogadva | 3/3 | 2ms | 3236 KiB | |||
10 | Elfogadva | 3/3 | 2ms | 3320 KiB | |||
11 | Elfogadva | 3/3 | 2ms | 3444 KiB | |||
12 | Elfogadva | 3/3 | 2ms | 3680 KiB | |||
13 | Elfogadva | 3/3 | 3ms | 3804 KiB | |||
14 | Elfogadva | 3/3 | 3ms | 3996 KiB | |||
15 | Elfogadva | 3/3 | 3ms | 4136 KiB | |||
16 | Elfogadva | 3/3 | 3ms | 4232 KiB | |||
17 | Elfogadva | 3/3 | 3ms | 4356 KiB |