本文共 1778 字，大约阅读时间需要 5 分钟。
题目链接：
给定n*m 的矩阵 常数k
以下一个n*m的矩阵，每一个位置由 0-9的一个整数表示
问：
从最后一行開始向上走到第一行使得路径上的和 % (k+1) == 0
每一个格子仅仅能向↖或↗走一步
求：最大的路径和
最后一行的哪个位置作为起点
从下到上的路径
思路：
简单dp
#include #include #include #include #include #include #include #include #include using namespace std;#define N 105#define inf 10000000#define ll intint 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];vector >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 = i+1, y = j-1; if(y>=1) { for(z = 0; z <= k; z++) if(dp[x][y][z] && sum[i][j][(z+mp[i][j])%k] < sum[x][y][z]+mp[i][j]) { dp[i][j][(z+mp[i][j])%k] = 1; px[i][j][(z+mp[i][j])%k] = x; py[i][j][(z+mp[i][j])%k] = y; sum[i][j][(z+mp[i][j])%k] = sum[x][y][z]+mp[i][j]; } } y = j+1; if(y<=m) { for(z = 0; z <= k; z++) if(dp[x][y][z] && sum[i][j][(z+mp[i][j])%k] < sum[x][y][z]+mp[i][j]) { dp[i][j][(z+mp[i][j])%k] = 1; px[i][j][(z+mp[i][j])%k] = x; py[i][j][(z+mp[i][j])%k] = y; sum[i][j][(z+mp[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] && anssum (posx, posy)); int tx = px[posx][posy][mod]; int ty = py[posx][posy][mod]; mod = ((mod-mp[posx][posy])%k+k)%k; posx = tx, posy = ty; } cout< < = 0; i--){ int nowx = ans[i].first, nowy = ans[i].second; if(nowy>y) printf("R"); else printf("L"); x = nowx, y = nowy; } puts(""); } return 0;}
转载地址：http://vwfxa.baihongyu.com/