数字三角形系列

2013年11月21日7,6461

数字三角形

题目描述

示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。　每一步可沿左斜线向下或右斜线向下走；　1< 三角形行数< 25；　三角形中的数字为整数< 1000；

输入

第一行为N，表示有N行后面N行表示三角形每条路的路径权

输出

路径所经过的数字的总和最大的答案

样例输入

5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

样例输出

提示

搜索80分，记忆化搜索AC

代码

#include<iostream> 
using namespace std; 
int main() 
{ 
int n; 
cin>>n; 
int a[n+1][n+1]; 
for(int i=1;i<=n;i++) 
   for(int j=1;j<=i;j++) 
      cin>>a[i][j]; 
for(int i=n-1;i>0;i--) 
   for(int j=1;j<=i;j++) 
      if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j]; 
      else a[i][j]+=a[i+1][j+1]; 
cout<<a[1][1]; 
return 0;
}

#include<iostream>

using namespace std;

int main()

{

int n;

cin>>n;

int a[n+1][n+1];

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++)

cin>>a[i][j];

for(int i=n-1;i>0;i--)

for(int j=1;j<=i;j++)

if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

cout<<a[1][1];

return 0;

}

数字三角形2

题目描述

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

输入

第1行n，表示n行 < =25 第2到n+1行为每个的权值

输出

mod 100最大值

样例输入

2 1 99 98

样例输出

代码

#include<iostream> 
using namespace std; 
int a[26][26][100]; 
int s[26][26];
int main() 
{ 
int n; 
cin>>n; 
for(int i=1;i<=n;i++) 
   for(int j=1;j<=i;j++) 
   {
    cin>>s[i][j];
   }
a[1][1][s[1][1]]=1;
for(int i=2;i<=n;i++)
    for(int j=1;j<=n;j++)
       for(int k=0;k<100;k++)
       {
          if(a[i-1][j][k]==1||(a[i-1][j-1][k]==1&&j-1>0)) a[i][j][k+s[i][j]]=1;
      }
for(int k=99;k>=0;k--)
   for(int i=1;i<=n;i++)
      if(a[n][i][k]==1){cout<<k;return 0;}
return 0;
}

#include<iostream>

using namespace std;

int a[26][26][100];

int s[26][26];

int main()

{

int n;

cin>>n;

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++)

{

cin>>s[i][j];

}

a[1][1][s[1][1]]=1;

for(int i=2;i<=n;i++)

for(int j=1;j<=n;j++)

for(int k=0;k<100;k++)

{

if(a[i-1][j][k]==1||(a[i-1][j-1][k]==1&&j-1>0)) a[i][j][k+s[i][j]]=1;

}

for(int k=99;k>=0;k--)

for(int i=1;i<=n;i++)

if(a[n][i][k]==1){cout<<k;return 0;}

return 0;

}

数字三角形3

题目描述

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

输入

第1行n，表示n行 < =25 第2到n+1行为每个的权值程序必须经过n div 2,n div 2这个点

输出

最大值

样例输入

2 1 1 1

样例输出

代码

#include<iostream>  
using namespace std;  
int main()  
{  
int n;  
cin>>n;  
int a[n+1][n+1];  
for(int i=1;i<=n;i++)  
   for(int j=1;j<=i;j++)  
      cin>>a[i][j];  
for(int i=n-1;i>0;i--)  
   for(int j=1;j<=i;j++)  
   {  
      if(i!=n/2||j==n/2)
      {
      if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j];  
      else a[i][j]+=a[i+1][j+1];  
  }
  else a[i][j]=-9999;
  }
cout<<a[1][1];  
return 0; 
}

#include<iostream>

using namespace std;

int main()

{

int n;

cin>>n;

int a[n+1][n+1];

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++)

cin>>a[i][j];

for(int i=n-1;i>0;i--)

for(int j=1;j<=i;j++)

{

if(i!=n/2||j==n/2)

{

if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

}

else a[i][j]=-9999;

}

cout<<a[1][1];

return 0;

}

数字三角形4

、

题目描述

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

输入

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

输出

最大值

样例输入

2 1 1 1 1 1

样例输出

代码

#include<iostream> 

using namespace std; 
int main() 
{ 
int n; 
int x,y;
cin>>n;
int a[26][26]; 
for(int i=1;i<=n;i++) 
   for(int j=1;j<=i;j++) 
   {
      cin>>a[i][j]; 
  }
      cin>>x>>y;
for(int j=1;j<=x;j++) 
   { 
      if(j!=y) a[x][j]=-9999;
   }

for(int i=n-1;i>0;i--) 
   for(int j=1;j<=i;j++) 
   { 
      if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j]; 
      else a[i][j]+=a[i+1][j+1]; 
   }
cout<<a[1][1]; 
return 0;
}

#include<iostream>

using namespace std;

int main()

{

int n;

int x,y;

cin>>n;

int a[26][26];

for(int i=1;i<=n;i++)

for(int j=1;j<=i;j++)

{

cin>>a[i][j];

}

cin>>x>>y;

for(int j=1;j<=x;j++)

{

if(j!=y) a[x][j]=-9999;

}

for(int i=n-1;i>0;i--)

for(int j=1;j<=i;j++)

{

if(a[i+1][j]>a[i+1][j+1])a[i][j]+=a[i+1][j];

else a[i][j]+=a[i+1][j+1];

}

cout<<a[1][1];

return 0;

}

« 「RQNOJ166」免费午餐城市交通 »

董希尧

膜拜黄哲威计算机巨神

hzwer.com _ Home | http://hzwer.com

数字三角形系列