原题:添加链接描述
#include#include using namespace std; const int N = 150; int n; int w[N][N]; int f[N][N][N];//f[x][y][z]表示到达下标之和为x(其中一个点纵坐标为y,另一个点纵坐标为z)的两条路径上取得的最大的和 int main() { cin>>n; int a, b, c; while(cin>>a>>b>>c, a || b || c) w[a][b] = c; for(int k = 2; k <= n + n; k ++ ){//k表示目前状态两条路的两个点的下标之和 for(int i1 = 1; i1 <= n; i1 ++ ){//i1表示第一条路的纵坐标值 for(int i2 = 1; i2 <= n; i2 ++ ){//i2表示第二条路的纵坐标值 int j1 = k - i1, j2 = k - i2;//分别求出两条路的横坐标值 if(j1 >= 1 &&j1 <= n && j2 >= 1 && j2 <= n){//如果目前两条路所处的点都在网格内 int t = w[i1][j1];//t表示到达目前这个点f值需要的增量,默认先算第一条路径可以经过,如果重合则第二条路径不能经过 if(i1 != i2) t += w[i2][j2];//如果两条路的点没有重合,增量就记上第二条路上的数值 int &x = f[k][i1][i2]; //每次循环代表两条路中的一条向前移动一格,所以上一状态应该是k-1 x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);//表示新状态是由两条路都向下移动一格产生的 x = max(x, f[k - 1][i1 - 1][i2] + t);//表示新状态是由第一条路向下,第二条路 向右移动产生的,因为第二条路向右,所以纵坐标不变,所以上一状态依然是i2 x = max(x, f[k - 1][i1][i2 - 1] + t);//同理,由第一路右移,第二路下移产生 x = max(x, f[k - 1][i1][i2] + t);//同理,由两条路都是右移产生 } } } } cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)