网站进行中英文转换怎么做,专业的网站建设,网站推广交换链接,展览设计题目链接#xff1a;点击打开链接 给定n*m 的矩阵 常数k 以下一个n*m的矩阵#xff0c;每一个位置由 0-9的一个整数表示 问#xff1a; 从最后一行開始向上走到第一行使得路径上的和 % (k1) 0 每一个格子仅仅能向↖或↗走一步 求#xff1a;最大的路径和 最后一行的哪个位… 题目链接点击打开链接 给定n*m 的矩阵 常数k 以下一个n*m的矩阵每一个位置由 0-9的一个整数表示 问 从最后一行開始向上走到第一行使得路径上的和 % (k1) 0 每一个格子仅仅能向↖或↗走一步 求最大的路径和 最后一行的哪个位置作为起点 从下到上的路径 思路 简单dp #include cstdio
#include algorithm
#includeiostream
#includestring.h
#include math.h
#includequeue
#includemap
#includevector
#includeset
using namespace std;
#define N 105
#define inf 10000000
#define ll int
int n,m,k;
int dp[N][N][12];
int px[N][N][12], py[N][N][12], sum[N][N][12];
int mp[N][N];
vectorpairint,int ans;
int main(){int i, j, z;while(~scanf(%d %d %d,n,m,k)){k;memset(sum, -1, sizeof sum);memset(px, -1, sizeof px);memset(py, -1, sizeof py);memset(dp, 0, sizeof dp);for(i 1; i n; i)for(j 1; j m; j)scanf(%1d,mp[i][j]);for(i 1; i m; i)dp[n][i][mp[n][i] % k] 1, sum[n][i][mp[n][i] % k] mp[n][i];for(i n-1; i ; i--){for(j 1; j m; j) {int x i1, y j-1;if(y1){for(z 0; z k; z)if(dp[x][y][z] sum[i][j][(zmp[i][j])%k] sum[x][y][z]mp[i][j]){dp[i][j][(zmp[i][j])%k] 1;px[i][j][(zmp[i][j])%k] x;py[i][j][(zmp[i][j])%k] y;sum[i][j][(zmp[i][j])%k] sum[x][y][z]mp[i][j];}}y j1;if(ym){for(z 0; z k; z)if(dp[x][y][z] sum[i][j][(zmp[i][j])%k] sum[x][y][z]mp[i][j]){dp[i][j][(zmp[i][j])%k] 1;px[i][j][(zmp[i][j])%k] x;py[i][j][(zmp[i][j])%k] y;sum[i][j][(zmp[i][j])%k] sum[x][y][z]mp[i][j];}}}}int posx 1, posy -1, mod 0, anssum -1;for(i 1; i m; i)if(dp[1][i][0] anssumsum[1][i][0])posy i, anssum sum[1][i][0];if(posy-1){puts(-1);continue;}ans.clear();while(posy!-1) {ans.push_back(pairint,int(posx, posy));int tx px[posx][posy][mod];int ty py[posx][posy][mod];mod ((mod-mp[posx][posy])%kk)%k;posx tx, posy ty;}coutanssumendl;int x ans[ans.size()-1].first, y ans[ans.size()-1].second;coutyendl;for(i ans.size()-2; i 0; i--){int nowx ans[i].first, nowy ans[i].second;if(nowyy)printf(R);else printf(L);x nowx, y nowy;}puts();}return 0;
}转载于:https://www.cnblogs.com/bhlsheji/p/5227280.html
