参考代码
#include <cstdio>
typedef long long LL;
const int N = 25;
int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
bool control[N][N];
LL dp[N][N];
int main()
{
int n, m, x, y;
scanf("%d%d%d%d", &n, &m, &x, &y);
for (int i = 0; i < 8; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx <= n && yy >= 0 && yy <= m) control[xx][yy] = true;
}
control[x][y] = true;
for (int i = 0; i <= m; i++) {
if (control[0][i]) break;
dp[0][i] = 1;
}
for (int i = 0; i <= n; i++) {
if (control[i][0]) break;
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (control[i][j]) dp[i][j] = 0;
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
printf("%lld\n", dp[n][m]);
return 0;
}
参考代码
#include <cstdio>
const int N = 35;
int dp[N][N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
dp[0][1] = 1;
for (int i = 1; i <= m; i++) {
dp[i][1] = dp[i - 1][n] + dp[i - 1][2];
dp[i][n] = dp[i - 1][n - 1] + dp[i - 1][1];
for (int j = 2; j < n; j++)
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
}
printf("%d\n", dp[m][1]);
return 0;
}
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int MOD = 1000007;
int a[N], dp[N][N], sum[N];
int getsum(int l, int r) {
return l > 0 ? (sum[r] + MOD - sum[l - 1]) % MOD : sum[r];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i <= m; i++) sum[i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++)
dp[i][j] = getsum(max(0, j - a[i]), j);
sum[0] = dp[i][0];
for (int j = 1; j <= m; j++) sum[j] = (sum[j - 1] + dp[i][j]) % MOD;
}
printf("%d\n", dp[n][m]);
return 0;
}
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
int a[N][N], dp[N][N];
int main()
{
int r;
scanf("%d", &r);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
dp[1][1] = a[1][1];
for (int i = 2; i <= r; i++) {
dp[i][1] = dp[i - 1][1] + a[i][1];
dp[i][i] = dp[i - 1][i - 1] + a[i][i];
for (int j = 2; j < i; j++)
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
}
int ans = 0;
for (int i = 1; i <= r; i++) ans = max(ans, dp[r][i]);
printf("%d\n", ans);
return 0;
}
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 55;
int dp[N][N][N][N], a[N][N];
int main()
{
int m, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= m; k++)
for (int l = 1; l <= n; l++)
dp[i][j][k][l] = -1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= m; k++) {
int l = i + j - k;
if (i * j * k * l == 1) dp[i][j][k][l] = a[1][1];
else {
// (i-1,j) (i,j-1)
// (k-1,l) (k,l-1)
int tmp = -1;
if (i > 1 && k > 1)
tmp = max(tmp, dp[i - 1][j][k - 1][l]);
if (i > 1 && l > 1)
tmp = max(tmp, dp[i - 1][j][k][l - 1]);
if (j > 1 && k > 1)
tmp = max(tmp, dp[i][j - 1][k - 1][l]);
if (j > 1 && l > 1)
tmp = max(tmp, dp[i][j - 1][k][l - 1]);
if (tmp == -1) dp[i][j][k][l] = -1;
else dp[i][j][k][l] = tmp + a[i][j] + a[k][l];
if (i == k && j == l && (i != m || j != n))
dp[i][j][k][l] = -1;
}
}
printf("%d\n", dp[m][n][m][n]);
return 0;
}
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1005;
const LL INF = 1e11;
int a[N][N];
LL dp[N][N][3]; // 0: from up, 1 from down, 2 from left
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -INF;
}
dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = a[1][1];
for (int i = 2; i <= n; i++) dp[i][1][0] = dp[i - 1][1][0] + a[i][1];
for (int j = 2; j <= m; j++) {
for (int i = 1; i <= n; i++) {
LL from = max(dp[i][j - 1][0], max(dp[i][j - 1][1], dp[i][j - 1][2]));
if (from != -INF) dp[i][j][2] = from + a[i][j];
}
for (int i = 2; i <= n; i++) {
LL from = max(dp[i - 1][j][0], dp[i - 1][j][2]);
if (from != -INF) dp[i][j][0] = from + a[i][j];
}
for (int i = n - 1; i >= 1; i--) {
LL from = max(dp[i + 1][j][1], dp[i + 1][j][2]);
if (from != -INF) dp[i][j][1] = from + a[i][j];
}
}
printf("%lld\n", max(dp[n][m][0], max(dp[n][m][1], dp[n][m][2])));
return 0;
}