AcWing 5973. 最佳路径
原题链接
困难
作者:
在月球_0
,
2024-11-04 23:44:20
,
所有人可见
,
阅读 12
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110,P = 11;
int n,m,p;
char w[N][N];
int dp[N][N][P];
int mod(int x)
{
x %= p + 1;
if(x < 0) x += p + 1;
return x;
}
int main()
{
cin >> n >> m >> p;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
cin >> w[i][j];
w[i][j] -= '0';
}
}
memset(dp, -0x3f, sizeof dp);
for(int i = 1;i <= m;i++)
dp[n][i][mod(w[n][i])] = w[n][i];
for(int i = n - 1;i >= 0;i--)
for(int j = 1;j <= m;j++)
for(int k = 0;k <= p;k++)
for(int u = j - 1;u <= j + 1;u += 2)
{
int t = w[i][j], &v = dp[i][j][k];
v = max(v, dp[i + 1][u][mod(k - t)] + t);
}
int c = 1;
for(int i = 2;i <= m;i++)
{
if(dp[1][i][0] > dp[1][c][0])
c = i;
}
if(dp[1][c][0] < 0) cout << -1 << endl;
else{
cout << dp[1][c][0] << endl;
//余数
int r = 0;
string path;
for(int i = 1;i < n;i++)
{
int t = w[i][c];
//r
if(dp[i + 1][c - 1][mod(r - t)] + t == dp[i][c][r])
{
path += 'R';
c--; r = mod(r - t);
}
else {
path += "L";
c++; r = mod(r - t);
}
}
reverse(path.begin(),path.end());
cout << c << endl;
cout << path << endl;
}
return 0;
}