首页 > 代码库 > 数字三角形2
数字三角形2
【题目描述】
现有一个数字三角形，从顶点遍历到底层，且必须经过某一个节点，询问其权值之和最大是多少。
【输入描述】
第一行输入一个整数n(n <= 25)，表示数字三角形的层数；
接下来n行，每行输入若干个数，表示每个节点的权值；
第n+2行输入两个数X、Y，表示必须经过的节点。
【输出描述】
输出一个数，表示答案。
【样例输入】
2
1
1 1
1 1
【样例输出】
2
DFS暴搜：
源代码：#include<cstdio>#include<algorithm>using namespace std;int n,T1,T2,i[26][26];int DFS(int X,int Y) //暴搜。{ if (X==T1&&Y!=T2) return -1000000000; //极限值代表此路不通。 if (X==n) return i[X][Y]; return i[X][Y]+max(DFS(X+1,Y),DFS(X+1,Y+1));}int main(){ scanf("%d",&n); for (int a=1;a<=n;a++) for (int b=1;b<=a;b++) scanf("%d",&i[a][b]); scanf("%d%d",&T1,&T2); printf("%d",DFS(1,1)); return 0;}
DP：
源代码：#include<cstdio>#include<algorithm>using namespace std;int n,Left,Right,Ans(0),i[26][26],f[26][26];int main(){ scanf("%d",&n); for (int a=1;a<=n;a++) for (int b=1;b<=a;b++) scanf("%d",&i[a][b]); scanf("%d%d",&Left,&Right); f[1][1]=i[1][1]; for (int a=2;a<=Left;a++) for (int b=1;b<=a;b++) f[a][b]=i[a][b]+max(f[a-1][b],f[a-1][b-1]); //同理于裸数字三角形。 for (int a=2;a<=n;a++) for (int b=1;b<Right;b++) f[a][b]=i[a][b]=0; //不可能。 for (int a=1;a<=n;a++) for (int b=1;b<=a;b++) if (a-b<Left-Right) f[a][b]=i[a][b]=0; //不可能。 for (int a=Left+1;a<=n;a++) for (int b=Right;b<=a;b++) f[a][b]=i[a][b]+max(f[a-1][b],f[a-1][b-1]); for (int a=1;a<=n;a++) Ans=max(Ans,f[n][a]); printf("%d",Ans); return 0;}
数字三角形2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。