求助,WA在第26个点
  • 板块CF41D Pawn
  • 楼主vcrlwpx
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/9/20 14:56
  • 上次更新2023/11/2 19:00:15
查看原帖
求助,WA在第26个点
216668
vcrlwpx楼主2023/9/20 14:56
#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = 15;
int n, m, k;
int a[N][N];
int dp[N][N][M];
bool from[N][N][M];
char s[N];
vector<int> v;
int ans = -1, pos = 0;

// from中0为左上,1为右上

int _mod(int x, int y) {
    return (x % y + y) % y;
}

int solve() {
    for (int i = 1; i <= m; i++)
        dp[n][i][_mod(a[n][i], k + 1)] = a[n][i];
    for (int i = n, nd; i > 1; i--)
        for (int j = 1; j <= m; j++) 
            for (int s = 0; s <= k; s++) if (dp[i][j][s] != -1) {
                int z = dp[i][j][s];
                if (j != 1) { // 尝试更新左上方元素
                    nd = _mod(s + a[i - 1][j - 1], k + 1);
                    int &t = dp[i - 1][j - 1][nd];
                    if (t <= z + a[i - 1][j - 1]) {
                        t = z + a[i - 1][j - 1];
                        from[i - 1][j - 1][nd] = 0;
                    }
                }
                if (j != n) { // 尝试更新右上方元素
                    nd = _mod(s + a[i - 1][j + 1], k + 1);
                    int &t = dp[i - 1][j + 1][nd];
                    if (t <= z + a[i - 1][j + 1]) {
                        t = z + a[i - 1][j + 1];
                        from[i - 1][j + 1][nd] = 1;
                    }
                }
            }

    for (int i = 1; i <= m; i++)
        if (dp[1][i][0] > ans) {
            ans = dp[1][i][0];
            pos = i;
        }
    if (ans == -1) return 0;
    
    int y = pos, d, cur = 0;
    for (int t = 1; t < n; t++) {
        d = from[t][y][cur];
        v.push_back(d);
        cur = _mod(cur - a[t][y], k + 1);
        y += (d == 0 ? 1 : -1);
    }
    pos = y;
    return 1;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s + 1;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j] - '0';
    }

    memset(dp, -1, sizeof(dp));
    
    if (!solve()) {
        puts("-1");
        return 0;
    }
    
    cout << ans << endl << pos << endl;
    reverse(v.begin(), v.end());
    for (int i = 0; i < n - 1; i++)
        cout << (v[i] == 0 ? 'L' : 'R');
    cout << endl;

	return 0;
}

2023/9/20 14:56
加载中...