POJ 2353 Ministry
题意：解题过程：AC代码：
POJ 2353 Ministry
题目传送门
题意：
给你一个n*m的矩阵，每个矩阵有一个数，表示在位置（i，j）办理手续的费用，在（i，j）办理完手续之后，你可以到（i+1，j）或者（i，j+1）或者（i，j-1）的位置继续办理手续，办完所有的手续定义为从（1，j）开始,到（n，j’）结束的整个过程，要求你求出办完手续的最小费用，并且输出方案。
解题过程：
我们首先可以想到DP的方法，但是对于（i，j）有三种转移的来源，为了不漏掉方案，我们可以对于每一行进行从左往右和从右往左的两次DP，然后用pre数组记录前缀用于输出方案就行了。
AC代码：
#pragma GCC optimize (3)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const ll inf=
1e15;
const int maxn=
505;
ll f[maxn][maxn];
int pre[maxn][maxn];
int n,m;
ll fee[maxn][maxn];
int main() {
scanf(
"%d%d",&n,&m);
for(
int i=
0;i<=n+
1;i++) {
for(
int j=
0;j<=m+
1;j++) {
fee[i][j]=inf;
}
}
for(
int i=
1;i<=n;i++) {
for(
int j=
1;j<=m;j++) {
scanf(
"%lld",&fee[i][j]);
pre[i][j]=j;
}
}
for(
int i=
0;i<=n;i++) {
for(
int j=
0;j<=m;j++) {
f[i][j]=inf;
}
}
for(
int i=
1;i<=m;i++) f[
1][i]=fee[
1][i];
for(
int i=
2;i<=n;i++) {
f[i][
1]=f[i-
1][
1]+fee[i][
1];
for(
int j=
2;j<=m;j++) {
if(f[i-
1][j]>f[i][j-
1]) {
pre[i][j]=j-
1;
}
f[i][j]=min(f[i-
1][j],f[i][j-
1])+fee[i][j];
}
ll temp=f[i][m];
f[i][m]=f[i-
1][m]+fee[i][m];
for(
int j=m-
1;j>=
1;j--) {
if(f[i][j+
1]+fee[i][j]<f[i][j]) {
pre[i][j]=j+
1;
}
f[i][j]=min(f[i][j],f[i][j+
1]+fee[i][j]);
}
f[i][m]=min(f[i][m],temp);
if(f[i][m]>temp) {
pre[i][m]=m-
1;
}
}
ll minx=inf;
int pos;
for(
int i=
1;i<=m;i++) {
if(f[n][i]<minx) {
minx=f[n][i];
pos=i;
}
}
int ii=n;
vector<int>ans;
ans.push_back(pos);
while(ii>
1) {
ans.push_back(pre[ii][pos]);
if(pos==pre[ii][pos]) {
ii--;
}
else {
pos=pre[ii][pos];
}
}
for(
int i=ans.size()-
1;i>=
0;i--) {
printf(
"%d\n",ans[i]);
}
return 0;
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433668.html
