动态规划——单向 DSP

xiaoxiao2021-02-28  11

题目传送门:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=52

题意:

给一个m行n列的矩阵,现让你从最左边走到最右边,求经过路径上的权值最小,并输出路径和最小值,如果有多条路径的权值和都是最小值,输出字典序最小的那一条

走的规则:

1.只能从当前列走到下一列

2.假设当前行是第i行,只能走到下一列的第i-1行、第i行、第i+1行

3.第一行的上一行是最后一行,最后一行的下一行是第一行

思路:

设置dp[i][j]是在第i行第i列时到最后一列的最小值,将整个图存在pl[m][n]里面,那么不难发现对任意一个位置有如下三种决策:

1.dp[i][j]=dp[i-1][j+1]+pl[i][j]

2.dp[i][j]=dp[i][j+1]+pl[i][j]

3.dp[i][j]=dp[i+1][j+1]+pl[i][j]

那么怎么记录路径呢???

可以用一个pos[m][n]来记录路径,其值是第i行第j列在满足最优情况下的下一个状态的行数。

#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <stack> #define INF 0x3f3f3f3f #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; int m, n; int pl[15][110]; int pos[15][110]; int dp[15][110]; int main() { while(~scanf("%d%d", &m, &n)) { memset(pl, 0, sizeof(pl)); memset(pos, 0, sizeof(pos)); for(int i=0; i<m; i++) for(int j=0; j<n; j++) scanf("%d", &pl[i][j]); for(int j=n-1; j>=0; j--) { for(int i=0; i<m; i++) { if(j==n-1) { dp[i][j]=pl[i][j]; continue; } int row[3]={i-1, i, i+1}; //用row数组保存三种决策的行 if(i==0) row[0]=m-1; if(i==m-1) row[2]=0; sort(row, row+3); //排序保证在值相同的情况下,字典序最小 dp[i][j]=INF; for(int k=0; k<3; k++) { int val=dp[row[k]][j+1]+pl[i][j]; if(val<dp[i][j]) { dp[i][j]=val; pos[i][j]=row[k]; //保存路径 } } } } int first; int ans=INF; for(int i=0; i<m; i++) //搜寻最小的值,同时从小到大地搜保证了字典序最小 if(ans>dp[i][0]) { ans=dp[i][0]; first=i; } printf("%d", first+1); //输出第一列的行数 for(int i=first, cnt=0; cnt<n-1; cnt++) { printf(" %d", pos[i][cnt]+1); i=pos[i][cnt]; } printf("\n%d\n", ans); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-250429.html

最新回复(0)