DP课题5 POJ 2353 Ministry
传送门:http://poj.org/problem?id=2353
翻译:
Mr. F. 想让部长批阅签署一份文件。但只有当部长的下属部门核准后,部长才签署一份文件。部门是一座M层的建筑物,从地面开始数起为1到M层。1<=M<=100.每一层有N个房间(1<=N<=500),也是从1到N编号。每一个房间里有且只有一个官员。一份文件要被部门签署,必须有至少一位(M层建筑物里的)官员签署;一个官员必须至少满足以下一项条件才能签署一个文件:
条件a:该官员在第一层工作。
条件b:该文件已经被楼下同一间房的官员签署。
条件c:该文件已经被隔壁的官员签署(所谓隔壁,是指同一层,且房间号相差为1。)
每一个官员签署一份文件,收取一点费用,这个费用为不超过10^9的正整数。
请找出签署一份文件要付出的最少费用。
分析:
这题与DP专题1中的题目有相似之处,只是这里改成了一个矩阵,我们可以设立状态dp[i][j]表示第到达第i行第j列的最低消耗,因为到达(i,j)有三种路径:从上到下,从左到右,从右到左。因此可以得到状态转移方程:dp[i][j]=Min{dp[i][j],dp[i][j+1]+a[i][j],dp[i][j-1]+input[i][j]}
但是这题的关键是要记录路径,而且要求在求出dp的最小耗费后,顺序输出,为了达到降维的目的,我们可以设立一个结构 point 记录每一点(i,j)的来历px和py,令第一行来自px = 0 ,这样px = 0 就可以作为结束的标志。顺序输出有两种方法,其一是递归,为了更加快速的解决问题,不建议采取递归,在这里我们在上一步找寻起点的过程中,从终点开始记录py的值,用trace数组记录。最户再逆序输出trace数组即可,这里的方法跟大数问题的处理有异曲同工之处。
代码如下:
/*Memory: 1064 KB Time: 46 MS Language: C Result: Accepted This source is shared by hust_lcl */ #include <stdio.h> #include <stdlib.h> int input[110][510]; int dp[110][510]; struct point{ int x , y ; } p[110][550]; int trace[100000]; int main() { int m , n , i , j , flag , k; //int a , b , c; scanf("%d%d",&m,&n); for(i = 1 ; i <= m ; i ++) for(j = 1 ; j <= n ; j ++) scanf("%d",&input[i][j]); for(i = 1 ; i <= n ; i ++) { dp[1][i] = input[1][i]; p[1][i].x = 0; p[1][i].y = i; } for(i = 2 ; i <= m ; i ++) { for(j = 1 ; j <= n ; j ++)//从上到下一次 { dp[i][j] = dp[i-1][j] + input[i][j]; p[i][j].x = i - 1 ; p[i][j].y = j; } for(j = 2 ; j <= n ; j ++)//从左到右一次 { if(dp[i][j] > dp[i][j-1] + input[i][j]) { dp[i][j] = dp[i][j-1] + input[i][j]; p[i][j].x = i ; p[i][j].y = j - 1 ; } } for(j = n - 1 ; j >= 1 ; j--)//从右到左一次 { if(dp[i][j] > dp[i][j+1] + input[i][j]) { dp[i][j] = dp[i][j+1] + input[i][j]; p[i][j].x = i; p[i][j].y = j + 1 ; } } } flag = dp[m][1]; j = 1; for(i = 2 ; i <= n ; i ++) if(flag > dp[m][i]) { flag = dp[m][i]; j = i ; } //printf("%d\n",flag); i = 1; trace[i++] = j; while(p[m][j].x!=0) { trace[i++] = p[m][j].y; k = m; m = p[m][j].x; j = p[k][j].y; } //j = 999; //while(!trace[j]) //j--; for(i -= 1; i >= 1 ; i --) printf("%d\n",trace[i]); return 0; }