首页 > 代码库 > poj 2353 双向dp(麻烦的办公室盖章)
poj 2353 双向dp(麻烦的办公室盖章)
题意:给定一个n*m的整数数组。现在要从第一行中的任意点移动到最后一行的任意点,要求每次只能移动一个距离(向左右或者向下,不能向上)。求路径所包含数值之和最小的时候的路径。
思路:dp。dp[i][j] 表示从第一行走到到第i行第j列这个位置的最小代价(路径包含的所有数值之和)。显然有dp[ i ][ j ] = min(dp[ i ][ j-1 ] , dp[ i ][ j+1 ] , dp[ i-1 ][ j ])+s[ i ][ j ]。s[i][j]表示此位置的数值。那么对于每一行,需要先从左向右做一边dp,然后从右向左做一遍。同时记录路径,递归输出。
#include <stdio.h> #include <string.h> #define INF 0x3fffffff #define N 105 #define M 505 int dp[2][M],s[N][M],path[N][M]; int n,m; void print(int n,int i){ if(n > 1){ if(path[n][i] == -1) print(n,i-1); else if(path[n][i] == 1) print(n,i+1); else print(n-1,i); } printf("%d\n",i); } int main(){ freopen("a.txt","r",stdin); while(scanf("%d %d",&n,&m)!=EOF){ int i,j,res; for(i = 1;i<=n;i++) for(j = 1;j<=m;j++) scanf("%d",&s[i][j]); memset(path,0,sizeof(path)); dp[0][0] = dp[0][m+1] = dp[1][0] = dp[1][m+1] = INF; for(j = 1;j<=m;j++) dp[0][j] = s[1][j]; for(i = 2;i<=n;i++){ for(j = 1;j<=m;j++){//从左向右 if(dp[1][j-1] < dp[0][j]){ dp[1][j] = dp[1][j-1]+s[i][j]; path[i][j] = -1;//表示从左边格子过来的 }else dp[1][j] = dp[0][j]+s[i][j]; } for(j = m;j>=1;j--){//从右向左 if(dp[1][j+1]+s[i][j] < dp[1][j]){ dp[1][j] = dp[1][j+1]+s[i][j]; path[i][j] = 1;//表示从右边格子过来的 } dp[0][j] = dp[1][j];//滚动数组 } } for(j = res = 1;j<=m;j++) if(dp[1][j] < dp[1][res]) res = j; print(n,res); } return 0; }
poj 2353 双向dp(麻烦的办公室盖章)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。