1498C — Planar Reflections

C. Planar Reflections

具体代码如下

#include<iostream>
#include<cstring>using namespace std;const int N = 1010, mod = 1e9 + 7;int n, k;
int dp[N][N][2];int solve(int cur, int k, int dir){if(k == 1) return 1;if(dp[cur][k][dir] != -1) return dp[cur][k][dir];int cnt = 2;//经过第一个平面会被分成两个if(dir == 1){if(cur < n)cnt = (cnt + solve(cur + 1, k, dir) - 1) % mod;//下一层的方案计算时会多算一次本层的方案，所以要减去1，下面同理if(cur > 1)cnt = (cnt + solve(cur - 1, k - 1, 0) - 1) % mod;dp[cur][k][dir] = cnt;}else{if(cur < n)cnt = (cnt + solve(cur + 1, k - 1, 1) - 1) % mod;if(cur > 1)cnt = (cnt + solve(cur - 1, k, dir) - 1) % mod;dp[cur][k][dir] = cnt;}return cnt;
}int main(){int T;cin >> T;while(T --){cin >> n >> k;memset(dp, -1, sizeof dp);cout << solve(1, k, 1) << endl;}return 0;
}