60分求助!
查看原帖
60分求助!
1079460
zjsdsb24楼主2023/9/26 18:46

我的代码如下,愿有大佬可以给出修改建议,多谢

#include <bits/stdc++.h>
using namespace std;
struct num{
	int N,fx,fy;
}f[10][10];
int g[10][10],n,ans;
int main(){
	int x,y,v;
	cin>>n;
	while(1){
		cin>>x>>y>>v;
		if(!x) break;
		g[x][y]=v;
	}
	for(int t=0;t<2;t++){//求两次
		f[1][1].N=g[1][1];
		//初始化动规表
		for(int i=2;i<=n;i++) f[1][i]=(num){f[1][i-1].N+g[1][i],1,i-1};
		for(int i=2;i<=n;i++) f[i][1]=(num){f[i-1][1].N+g[i][1],i-1,1};
		//求解每一遍最大的数,并记录路径
		for(int i=2;i<=n;i++) for(int j=2;j<=n;j++){
			if(f[i-1][j].N>=f[i][j-1].N) f[i][j]=(num){f[i-1][j].N+g[i][j],i-1,j};
			else f[i][j]=(num){f[i][j-1].N+g[i][j],i,j-1};
		}
		ans+=f[n][n].N;//加上该次所求结果
		if(t) break;//第二次无需执行下面代码,退出
		//以下代码作用:顺藤摸瓜,将路径上各位置置于0
		x=y=n;//由终点开始
		while(x>1 || y>1){//寻找至起点
			g[x][y]=0;
			x=f[x][y].fx;
			y=f[x][y].fy;
		}
		g[1][1]=0;
	}
	cout<<ans;
	return 0;
}
2023/9/26 18:46
加载中...