| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 604980 | snasibov05 | 캥거루 (CEOI16_kangaroo) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2005;
const int m = 1e9 + 7;
int dp[mxn][mxn][mxn][2];
int pref[mxn][mxn][mxn][2];
int suf[mxn][mxn][mxn][2];
// dir : 0 -> left, 1 -> right;
void calc(int sz, int st, int fn, int dir){
if (dp[sz][st][fn][dir] != -1) return;
if (st == fn) {
if (sz == 1) dp[sz][st][fn][dir] = 1;
else dp[sz][st][fn][dir] = 0;
return;
}
dp[sz][st][fn][dir] = 0;
if (dir == 0){
for (int to = 1; to < st; ++to){
if (st < fn) {
calc(sz - 1, to, fn - 1, 1);
dp[sz][st][fn][dir] += dp[sz - 1][to][fn - 1][1];
dp[sz][st][fn][dir] %= m;
}
else {
calc(sz - 1, to, fn, 1);
dp[sz][st][fn][dir] += dp[sz - 1][to][fn][1];
dp[sz][st][fn][dir] %= m;
}
}
} else{
for (int to = st+1; to <= sz; ++to){
if (st < fn) {
calc(sz - 1, to - 1, fn - 1, 0);
dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn - 1][0];
dp[sz][st][fn][dir] %= m;
}
else {
calc(sz - 1, to - 1, fn, 0);
dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn][0];
dp[sz][st][fn][dir] %= m;
}
}
}
}
int main() {
int n, cs, cf; cin >> n >> cs >> cf;
dp[1][1][1][0] = dp[1][1][1][1] = 1;
pref[1][1][1][0] = pref[1][1][1][1] = 1;
suf[1][1][1][0] = suf[1][1][1][1] = 1;
for (int sz = 2; sz <= n; ++sz){
for (int fn = 1; fn <= sz; ++fn){
for (int st = 1; st <= sz; ++st){
if (st == fn) continue;
if (st < fn) {
dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn - 1][1];
dp[sz][st][fn][0] %= m;
} else{
dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn][1];
dp[sz][st][fn][0] %= m;
}
if (st < fn) {
dp[sz][st][fn][1] += suf[sz - 1][st][fn - 1][0];
dp[sz][st][fn][1] %= m;
} else{
dp[sz][st][fn][1] += suf[sz - 1][st][fn][0];
dp[sz][st][fn][1] %= m;
}
}
for (int st = 1; st <= sz; ++st) pref[sz][st][fn][1] = (pref[sz][st-1][fn][1] + dp[sz][st][fn][1]) % m;
for (int st = sz; st > 0; --st) suf[sz][st][fn][0] = (suf[sz][st+1][fn][0] + dp[sz][st][fn][0]) % m;
}
}
int ans = dp[n][cs][cf][0] + dp[n][cs][cf][1];
ans %= m;
cout << ans << "\n";
return 0;
}