头像

acwing_248




离线:4天前


活动打卡代码 AcWing 898. 数字三角形

题目描述
给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。

7

3 8
8 1 0
2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n,表示数字三角形的层数。

接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数,表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30

C++ 代码
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
define MAX 500
using namespace std;
int main()
{
int n,a[MAX][MAX],b[MAX][MAX];
long int s = 0;
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)
b[n][i] = a[n][i];
for(int i = n-1;i;i–)
for(int j = 1;j <= i;j)
b[i][j] = max(b[i+1][j] + a[i][j],b[i+1][j+1] + a[i][j]);
cout<<b[1][1]<<endl;
}




题目描述

给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。

    7
  3   8
8   1   0

2 7 4 4
4 5 2 6 5
输入格式
第一行包含整数n,表示数字三角形的层数。

接下来n行,每行包含若干整数,其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数,表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例:
30

C++ 代码

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

define MAX 500

using namespace std;
int main()
{
int n,a[MAX][MAX],b[MAX][MAX];
long int s = 0;
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)
b[n][i] = a[n][i];
for(int i = n-1;i;i–)
for(int j = 1;j <= i;j
)
b[i][j] = max(b[i+1][j] + a[i][j],b[i+1][j+1] + a[i][j]);
cout<<b[1][1]<<endl;
}




题目描述

在一条数轴上有 N 家商店,它们的坐标分别为 A1~AN。

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数N。

第二行N个整数A1~AN。

输出格式
输出一个整数,表示距离之和的最小值。

数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例:
4
6 2 9 1
输出样例:
12

c++代码

include[HTML_REMOVED]

define MAX 100000

using namespace std;

int main(){
int a[MAX],max = 0;
long int i;
cin>>i;
for(int j = 0;j < i;j)
{
cin>>a[j];
}
sort(a,a+i);
long int s = 0;
int min;
min = a[i/2 ];
for(long int k1 = 0;k1 < i;k1
)
s +=abs(a[k1] - min);
cout<<s<<endl;
return 0;
}



活动打卡代码 AcWing 104. 货仓选址

include[HTML_REMOVED]

define MAX 100000

using namespace std;
void insert(int *a,long int n)
{
long int i,j,temp;
for(i=1;i[HTML_REMOVED]=0&&temp[HTML_REMOVED]>i;
for(int j = 0;j < i;j++)
{
cin>>a[j];
}
insert(a,i);

 long long  s = 0;

 int min= a[i/2];
for(long int k1 = 0;k1 < i;k1++)
    s +=abs(a[k1] - min);
 cout<<s<<endl;
 return 0;

}