数字三角形W,问题合集

2189 数字三角形W,2189三角形w

1220 数字三角形

时光限定: 1
s    空间限制: 12玖仟KB    标题等级 : 黄金高尔德

标题汇报 Description

如图所示的数字三角形,从最上部出发,在每一结点能够挑选向左走或得向右走,一向走到底层,供给找寻一条路径,使路线上的值最大。

澳门葡京备用网址 1

输入描述 Input Description

先是行是数塔层数N(1<=N<=100)。

第二行起,按数塔图形,有一个或三个的子弹头,表示该层节点的值,共有N行。

输出描述 Output Description

输出最大值。

样例输入 Sample Input

5

13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

样例输出 萨姆ple Output

86

数码范围及提示 Data Size & Hint

数字三角形

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int w[157][157],n; 
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++)
10       for(int j=1;j<=i;j++)
11         scanf("%d",&w[i][j]);
12     for(int i=n-1;i>=1;i--)
13       for(int j=1;j<=i;j++)
14         w[i][j]+=max(w[i+1][j],w[i+1][j+1]);
15     printf("%d",w[1][1]);
16     return 0;
17 }

嘟!数字三角形 W WW WWW集结!,ww

哔!数字三角形全部会集!

数字三角形!到!

数字三角形W!到!

数字三角形WW!到!

数字三角形WWW!到!


数字三角形,三个灰常灰常规范的动规题,是一道灰常灰常水的动规题,

2189 数字三角形W

时限: 1 s 空间范围: 3三千 KB 标题品级 : 白银 Gold 标题陈诉Description

数字三角形
供给走到结尾mod 100最大

输入描述 Input Description

第1行n,表示n行
第2到n+1行为每个的权值

输出描述 Output Description

mod 100最大值

样例输入 Sample Input

2
1
99 98

样例输出 Sample Output

99

数据范围及提醒 Data Size & Hint

n<=25

2189 数字三角形W

 

时限: 1 s
空间范围: 3两千 KB 标题等第 : 白银 Gold       标题陈说 Description

数字三角形
务求走到终极mod 100最大

输入描述 Input Description

第1行n,表示n行
第2到n+1行为每种的权值

数字三角形W,问题合集。输出描述 Output Description

mod 100最大值

样例输入 Sample Input

2
1
99 98

样例输出 萨姆ple Output

99

数码范围及指示 Data Size & Hint

n<=25

2189 数字三角形W

日子范围: 1
s    空间范围: 3三千KB    题目品级 : 黄金高尔德

主题素材陈诉 Description

数字三角形
要求走到最终mod 100最大

输入描述 Input Description

第1行n,表示n行
第2到n+1行为每一种的权值

出口描述 Output Description

mod 100最大值

样例输入 Sample Input

2
1
99 98

样例输出 Sample Output

99

数量范围及提醒 Data Size & Hint

n<=25

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 const int p=100;
 6 int w[35][35],n,f[35][35][105]; 
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;i++)
11       for(int j=1;j<=i;j++)
12         scanf("%d",&w[i][j]);
13     f[1][1][ ((w[1][1]%p) + p)%p ]=1;
14     
15     for(int i=2;i<=n;i++)
16       for(int j=1;j<=i;j++)
17        for(int k=0;k<=99;k++)
18          f[i][j][k]=f[i-1][j][( ( k-w[i][j]) %p+p ) %p ]||
19            f[i-1][j-1][( ( k-w[i][j]) %p+p ) %p ];
20     int maxx=0;
21     for(int i=1;i<=n;i++)
22       for(int j=99;j>=0;j--)
23         if(f[n][i][j]) maxx=max(maxx,j);
24     printf("%d",maxx);
25     return 0;
26 }

1220 数字三角形

 

 时限: 1
s  空间范围: 127000KB  标题等第 : 黄金高尔德   标题汇报 Description

如图所示的数字三角形,从顶端出发,在每一结点能够选用向左走或得向右走,一向走到底层,需求搜索一条路子,使路线上的值最大。

澳门葡京备用网址 2
输入描述 Input Description

第一行是数塔层数N(1<=N<=100)。

其次行起,按数塔图形,有一个或八个的整数,表示该层节点的值,共有N行。

出口描述 Output Description

出口最大值。

样例输入 萨姆ple Input

5

13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

样例输出 Sample Output

86

 

话相当的少说上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n;
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
  for (int j=1;j<=i;j++)
   cin>>a[i][j];
 for (int i=n-1;i>=1;--i)
  for (int j=1;j<=i;j++)
   a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
 cout<<a[1][1];
 return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------
重点说的是后三个转换型的题,我们先跳过 数字三角形W ,先来看数字三角形WW和WWW;
其实这两道题也是水题,先看题目:

分类标签 Tags 点此举办

最终一维记录那个数%p可不大概到达

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=26; 6 int n; 7 int a[MAXN][MAXN]; 8 bool f[MAXN][MAXN][101]; 9 int main()10 {11     scanf("%d",&n);12     for(int i=1;i<=n;i++)13         for(int j=1;j<=i;j++)14             cin>>a[i][j];15     16     for(int i=1;i<=n;i++)f[n][i][a[n][i]%100]=1;17     18     for(int i=n-1;i>=1;i--)19         for(int j=1;j<=i;j++)20             for(int k=0;k<=99;k++)21             f[i][j][k]=f[i+1][j][(k-a[i][j]+100)%100]||f[i+1][j+1][(k-a[i][j]+100)%100];22     23     for(int k=100;k>=1;k--)24         if(f[1][1][k]==1){cout<<k;break;}25     return 0;26 }

分拣标签 Tags 点此展开

末尾一维记录这一个数%p可不也许达到

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int MAXN=26;
 6 int n;
 7 int a[MAXN][MAXN];
 8 bool f[MAXN][MAXN][101];
 9 int main()
10 {
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)
13         for(int j=1;j<=i;j++)
14             cin>>a[i][j];
15     
16     for(int i=1;i<=n;i++)f[n][i][a[n][i]%100]=1;
17     
18     for(int i=n-1;i>=1;i--)
19         for(int j=1;j<=i;j++)
20             for(int k=0;k<=99;k++)
21             f[i][j][k]=f[i+1][j][(k-a[i][j]+100)%100]||f[i+1][j+1][(k-a[i][j]+100)%100];
22     
23     for(int k=100;k>=1;k--)
24         if(f[1][1][k]==1){cout<<k;break;}
25     return 0;
26 }

 

数字三角形W,2189三角形w 2189 数字三角形W
时间限定: 1 s 空间范围: 3两千 KB 题目等第 : 白银 高尔德 标题叙述Description 数字三角形 须求走到…

说实话那道题笔者不清楚是或不是动态规划,那DP亦不是自己写的(大概是数据太水把自身放过去了),小编以为那不满足动态规划无后效性的标准化,望大神路过留言。。。

193 数字三角形WW

 

 时限: 1
s  空间限制: 3两千KB  题目等级 : 钻石
Diamond    标题汇报 Description

数字三角形必得经过某多个点,使之走的行程和最大

输入描述 Input Description

第1行n,表示n行
第2到n+1行为每一种的权值
前后相继必得透过n div 2,n div 2那些点

出口描述 Output Description

最大值

样例输入 Sample Input

2
1
1 1

样例输出 Sample Output

2

多少范围及提示 Data Size & Hint

n <=25

 

渴求必需经过(n/2,n/2)那个点的话,那我们只需把那么些点的值先加上贰个十分大的数,

最终只需给结荚减去你给它丰裕的值就好了,水题直接上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n;
bool f[110][110]={0};
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
  for (int j=1;j<=i;j++)
   {
    cin>>a[i][j];
   }
 a[n/2][n/2]+=5000;
 for (int i=n-1;i>=1;--i)
  for (int j=1;j<=i;j++)
   a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
 cout<<a[1][1]-5000;
 return 0;
}

2193 数字三角形WW

光阴限制: 1
s    空间限制: 3两千KB    标题等级 : 钻石
Diamond

主题素材陈诉 Description

数字三角形必需通过某二个点,使之走的路途和最大

输入描述 Input Description

第1行n,表示n行
第2到n+1行为每一种的权值
程序必需经过n div 2,n div 2这一个点

输出描述 Output Description

最大值

样例输入 Sample Input

2
1
1 1

样例输出 萨姆ple Output

2

数码范围及提醒 Data Size & Hint

n <=25

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,x,y,w[35][35],ko;
long long f[35][35];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        scanf("%d",&w[i][j]);
    f[1][1]=w[1][1];
    w[n/2][n/2]+=99999999;
    for(int i=2;i<=n;i++)
      for(int j=1;j<=i;j++)
        f[i][j]=w[i][j]+max(f[i-1][j],f[i-1][j-1]);
    long long ans=0;
    for(int i=1;i<=n;i++)
      ans=max(ans,f[n][i]);
    printf("%lld",ans-99999999);
    return 0;
}

这一次是正推。。

2198 数字三角形WWW

 

 时限: 1
s  空间限制: 33000KB  标题品级 : 钻石
Diamond    标题陈说 Description

数字三角形必需经过某二个点,使之走的行程和最大

输入描述 Input Description

第1行n,表示n行 
第2到n+1行为各个的权值
第n+2行为八个数x,y表示必得通过的点

出口描述 Output Description

最大值

样例输入 Sample Input

2
1
1 1
1 1

样例输出 萨姆ple Output

2

多少范围及提示 Data Size & Hint

n<=25

那题思路与WW同样同样滴,只是把必走的点变为了(x,y),

上代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[110][110]={0},n,x,y;
bool f[110][110]={0};
int main()
{
 cin>>n;
 for (int i=1;i<=n;i++)
  for (int j=1;j<=i;j++)
    cin>>a[i][j];
 cin>>x>>y;
 a[x][y]+=5000;
 for (int i=n-1;i>=1;--i)
  for (int j=1;j<=i;j++)
   a[i][j]=max(a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]);
 cout<<a[1][1]-5000;
 return 0;
}
--------------------------------------------------------------------------------------------------------------------------------------------------------
到了最重点的题:数字三角形W,这个题一开始我并没有想出较简单做法,后来敬爱的学哥学姐教会了我,因为毕竟我也是个蒟蒻啊...具体做法在代码中解释吧。

2198 数字三角形WWW

光阴限制: 1
s    空间限制: 3两千KB    标题等第 : 钻石
Diamond

主题素材陈说 Description

数字三角形必得通过某二个点,使之走的里程和最大

输入描述 Input Description

第1行n,表示n行 
第2到n+1行为每一种的权值
第n+2行为五个数x,y表示必得透过的点

出口描述 Output Description

最大值

样例输入 Sample Input

2
1
1 1
1 1

样例输出 萨姆ple Output

2

数量范围及提示 Data Size & Hint

n<=25

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,x,y,w[35][35],ko;
long long f[35][35];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=i;j++)
        scanf("%d",&w[i][j]);
    scanf("%d%d",&x,&y);
    w[x][y]+=99999999;
    f[1][1]=w[1][1];
    for(int i=2;i<=n;i++)
      for(int j=1;j<=i;j++)
        f[i][j]=w[i][j]+max(f[i-1][j],f[i-1][j-1]);
    long long ans=0;
    for(int i=1;i<=n;i++)
      ans=max(ans,f[n][i]);
    printf("%lld",ans-99999999);
    return 0;
}

 

2189 数字三角形W

 

 时限: 1
s  空间范围: 3三千KB  标题品级 : 白金高尔德   标题陈述 Description

数字三角形
渴求走到最终mod 100最大

输入描述 Input Description

第1行n,表示n行
澳门葡京备用网址 ,第2到n+1行为每一个的权值

出口描述 Output Description

mod 100最大值

样例输入 山姆ple Input

2
1
99 98

样例输出 Sample Output

99

数量范围及提醒 Data Size & Hint

n<=25

代码:

//笔者是用的倒推的思路做的,顺推其实思路一致,转变一下就好,这里只给出倒推得代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[26][26]={0};
bool f[26][26][100]={0};
int main()
{
cin>>n;
for (int i=1;i<=n;i++) //数据的读入
for (int j=1;j<=i;j++)
cin>>a[i][j];
for (int i=1;i<=n;i++) //这一步的代码是为了将最后一排的有着数存下来
f[n][i][a[n][i]]=true;
for (int i=n-1;i>=1;–i)
//这里是器重进度,思路:将具有的或然性mod100都存下来,
for (int j=1;j<=i;j++)
for (int k=0;k<=99;k++)
{
if (f[i+1][j][k])
f[i][j][(k+a[i][j])%100]=true;
if (f[i+1][j+1][k])
f[i][j][(k+a[i][j])%100]=true;
}
for (int k=99;k>=0;–k)
//寻觅富有异常的大可能自便中最大的或者,输出,这些题就AC咯、
if (f[1][1][k])
{
cout<<k;
return 0;
}
}

W WW WWW会集!,ww
哔!数字三角形全部集结! 数字三角形!到! 数字三角形W!到!
数字三角形WW!到! 数字三角形WWW!到…

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website