回档|数字三角形3,4

描述

    数字三角形必须经过某一个点，使之走的路程和最大

输入格式

第1行n，表示n行 <=25
第2到n+1行为每个的权值
第n+2行为两个数x,y表示必须经过的点

输出格式
一个值，经过x,y的最大路

测试样例1

输入
2
1
1 1
1 1
输出
2

备注
各个测试点1s

 

题目分析：
    这道题我做的很暴力，直接把第x行上除了y的点都赋值成-的极大值，然后就过了……
   （3和4的区别是3要求过一个定点n/2,n/2）

源代码：

#include<iostream>
using namespace std;
int map[26][26],f[26][26];
int max(int a,int b)
{
 if (a>b) return a;
   else return b;
}
int main()
{
 int n;
 cin >> n;
 for (int i=1; i<=n; i++)
   for (int j=1; j<=i; j++)
     cin >> map[i][j];
 int x,y;
 cin >> x >> y;
 for (int i=1; i<=x; i++) if (i != y) map[x][i]=-10000007;
 for (int i=1; i<=n; i++)
   for (int j=1; j<=i; j++)
     f[i][j]=max(f[i-1][j],f[i-1][j-1])+map[i][j];
 int ans=0;
    for (int i=1; i<=n; i++) if (f[n][i]>ans) ans=f[n][i];
 cout << ans;
 return 0;
}