首页 > 代码库 > 数字三角形

数字三角形

2024-08-18 07:56:08   213人阅读

【题目描述】

现有一个数字三角形，询问从其顶点遍历到底层的权值之和 mod 100的值最大是多少。

【输入描述】

第一行输入n(n <= 25)，表示数字三角形的层数；

接下来n行，每行输入若干个数，表示每个节点的权值。

【输出描述】

输出一个数，表示答案。

【样例输入】

2

1

99 98

【样例输出】

99

 

DFS暴搜：

源代码：#include<cstdio>#include<algorithm>using namespace std;int n,Ans(0),i[26][26];void DFS(int X,int Y,int S) //暴力搜索。{    if (X==n)    {        Ans=max(Ans,S%100);        return;    }    DFS(X+1,Y,S+i[X+1][Y]);    DFS(X+1,Y+1,S+i[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]);    DFS(1,1,i[1][1]);    printf("%d",Ans);    return 0;}

 

类DP：

源代码：#include<cstdio>int n,Ans(0),i[26][26];bool f[26][26][100];int main() //用bool来存储此状态合不合法。{    scanf("%d",&n);    for (int a=1;a<=n;a++)      for (int b=1;b<=a;b++)        scanf("%d",&i[a][b]);    f[1][1][i[1][1]%100]=true;    for (int a=2;a<=n;a++)      for (int b=1;b<=a;b++)        for (int c=1;c<=99;c++) //值得学习，这个循环将上一层的所有可能都保留了下并进行了拓展。        {            int t=c-i[a][b];            if (t<0)              t+=100;            f[a][b][c]=f[a-1][b-1][t]||f[a-1][b][t];        }    for (int b=1;b<=n;b++)      for (int c=i[n][b];c<=99;c++)        if (f[n][b][c]&&c>Ans)          Ans=c;    printf("%d",Ans);    return 0;}

数字三角形


联系
我们