P1216 数字三角形
本文最后修改于 761 天前,部分内容可能已经过时!
最近在学dp,于是选了这一题。这题暴力似乎也能打,但还没打(估计是咕咕咕了),既能练dp还能练dfs,岂不美哉?
P1216 [USACO1.5]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大
输入输出格式
输入格式:
第一个行包含 R(1<= R<=1000) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
输出格式:
单独的一行,包含那个可能得到的最大的和。
输入输出样例
输入样例#1:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例#1:
30
说明
题目翻译来自NOCOW。
USACO Training Section 1.5
解题
7-3-8-7-5 求和是30
方法1:递归枚举暴力
每一条路径都走一遍。
dfs(1,1,7)->dfs(2,1,7)->dfs(2,2,7)->dfs(3,1,10)->……->dfs(n,1,sum)
比较最大值,存入answer。
方法2:dp
瞎推了一包东西,然后发现了什么
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
0 0 0 0 7 0 0
0 0 0 10 15 0 0
0 0 18 11 16 0 0
0 20 25 20 19 0 0
24 30 22 26 24 0 0
a[n]={7,10,15,18,11,16,20,25,20,19,24,30,22,26,24}
先读入一组数据,再求和,取最大值。
试了下写比大小,发现并不能写出来,这里max还是伪代码,没有实际作用
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1002],result=0;
int main() {
scanf("%d",&n);
for (int i=n;i;i--) //5->1 共5层
for (int j=i;j<=n;j++) { //
scanf("%d",&m);
a[j]=max(a[j+1],a[j])+m; //dp 找最大 每次读入都将上一层的数据和求和
}
for (int i=0;i<=n;i++)
result=max(result,a[i]);
printf("%d",result);
return 0;
}
然后参考题解,发现了这个:
int max(int &x,int &y){return x>y?x:y;}
我佛了!!!!!!不知道哪里挂了!!!!!!
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m,a[1002],result=0;
scanf("%d",&n);
for (int i=n;i>=1;i--) //5->1 共5层
for (int j=i;j<=n;j++) { //从i到n,读入n-i次
scanf("%d",&m);
a[j]=max(a[j+1],a[j])+m; //dp 找最大 每次读入都将上一层的数据和求和
}
for (int i=0;i<=n;i++)
result=max(result,a[i]);
printf("%d",result);
return 0;
}
啊啊啊啊啊
然后试了下memset,发现并没有用
玄学错误
11:55分清醒过来了
然后
MD这是大忌啊 int怎么能放在里面呢???
同样一个INT类型定义在main函数里和main函数外面有什么区别
#include <bits/stdc++.h>
using namespace std;
int max(int &x,int &y){return x>y?x:y;}
int n,m,a[1002],result=0;
int main() {
scanf("%d",&n);
for (int i=n;i;i--) //5->1 共5层
for (int j=i;j<=n;j++) { //
scanf("%d",&m);
a[j]=max(a[j+1],a[j])+m; //dp 找最大 每次读入都将上一层的数据和求和
}
for (int i=0;i<=n;i++)
result=max(result,a[i]);
printf("%d",result);
return 0;
}
然后...过了
后记
还是要提高码力...我太弱了...
物理已经让我心力交瘁,现在不知道能不能救得过来,救不过来就只能学文了...
还是得拿出时间写题