|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <cstdio> #define MX 100000000 using namespace std; int r,c; int input[11][101]; int dp[11][101]; int next_row[11][101]; int main() { int tmp,temp_position,row; while(scanf("%d%d",&r,&c)==2) { for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin>>input[i][j]; for(int i=0;i<r;i++) dp[i][c-1]=input[i][c-1]; for(int i=c-2;i>=0;i--) { for(int j=0;j<r;j++) { tmp=MX; for(int k=-1;k<=1;k++) { temp_position = (j+k+r)%r; if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i])) { next_row[j][i]=temp_position; tmp = dp[temp_position][i+1]; } } dp[j][i]=input[j][i]+tmp; } } tmp = MX; for(int i=0;i<r;i++) { if(tmp>dp[i][0]) { tmp = dp[i][0]; row = i; } } cout<<row+1; for(int i=0;i<c-1;i++) { row = next_row[row][i]; cout<<" "<<row+1; } cout<<"\n"<<tmp<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <cstdio> #define MX 100000000 using namespace std; int r,c; int input[11][101]; int dp[11][101]; int next_row[11][101]; int main() { int tmp,temp_position,row; while(scanf("%d%d",&r,&c)==2) { for(int i=0;i<r;i++) for(int j=0;j<c;j++) cin>>input[i][j]; for(int i=0;i<r;i++) dp[i][c-1]=input[i][c-1]; for(int i=c-2;i>=0;i--) { for(int j=0;j<r;j++) { tmp=MX; for(int k=-1;k<=1;k++) { temp_position = (j+k+r)%r; if(tmp>dp[temp_position][i+1] || (tmp==dp[temp_position][i+1] && temp_position<next_row[j][i])) { next_row[j][i]=temp_position; tmp = dp[temp_position][i+1]; } } dp[j][i]=input[j][i]+tmp; } } tmp = MX; for(int i=0;i<r;i++) { if(tmp>dp[i][0]) { tmp = dp[i][0]; row = i; } } cout<<row+1; for(int i=0;i<c-1;i++) { row = next_row[row][i]; cout<<" "<<row+1; } cout<<"\n"<<tmp<<"\n"; } return 0; } |