为什么错3个点。。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <climits>
#include <ctime>
#include <stack>
#include <iostream>
using namespace std;
int m,n,cost[101][501],f[101][501],endy,ans;
pair<int,int> way[101][501],p,ed;
stack<int> ansy;
int main()
{
ed=make_pair(0,0);
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++) scanf("%d",&cost[i][j]);
for(int i=1;i<=n;i++) f[1][i]=cost[1][i],way[1][i]=ed;
for(int i=1;i<=m;i++) f[i][0]=f[i][n+1]=INT_MAX;
for(int i=2;i<=m;i++)
for(int j=1;j<=n;j++){
if(f[i][j-1]<f[i-1][j]) way[i][j]=make_pair(i,j-1),f[i][j]=f[i][j-1]+cost[i][j];
else way[i][j]=make_pair(i-1,j),f[i][j]=f[i-1][j]+cost[i][j];
}
for(int i=2;i<=m;i++)
for(int j=n;j>=1;j--){
if(f[i][j+1]<f[i-1][j]) way[i][j]=make_pair(i,j+1),f[i][j]=f[i][j+1]+cost[i][j];
else way[i][j]=make_pair(i-1,j),f[i][j]=f[i-1][j]+cost[i][j];
}
ans=INT_MAX;
for(int i=1;i<=n;i++) if(f[m][i]<ans) ans=f[m][i],endy=i;
ansy.push(endy);
p=way[m][endy];
while(p!=ed)
{
ansy.push(p.second);
p=way[p.first][p.second];
}
while(!ansy.empty()) printf("%d\n",ansy.top()),ansy.pop();
system("pause");
return 0;
}

1 条评论

  • @ 2018-09-28 19:47:35

    我WA了6、8点,气得不行,这里又没有数据下载

  • 1

信息

ID
1139
难度
7
分类
动态规划 点击显示
标签
递交数
4495
已通过
782
通过率
17%
上传者