树形DPCSU 1022: 菜鸟和大牛
目录
一，树形DP
以树作为动态规划的良基集合的问题，称为树形DP
二，OJ实战
CSU 1022: 菜鸟和大牛
题目：
blue和AutoGerk是好朋友。他们的相同点是都喜欢研究算法，不同点是AutoGerk已是大牛而blue还是菜鸟。blue经常拿一些自以为很难的问题去问AutoGerk，想难倒他，但是每次AutoGerk都能轻而易举地做出来。就在上个礼拜的星期天下午，AutoGerk正在玩游戏，blue又拿着他的问题来了。AutoGerk一看，依然是如此简单。AutoGerk很想玩他的游戏，但是又不想冷落朋友。于是他介绍你，同样是大牛级的人物，给blue，来回答他的问题。
blue的问题如下：
一个由n行数字组成的三角形，第i行有2i-1个正整数（小于等于1000），如下：
3
7 1 4
2 4 3 6 2
8 5 2 9 3 6 2
要求你用笔从第1行画到第n（0 < n ≤ 100）行，从当前行往下画的时候只能在相邻的数字经过，也就是说，如果从一行的一个数往下画，只能选择其左下或者正下或者右下三个数中的一个（如果存在的话），把所有被画起来的数字相加，得到一个和，求能得到的最大的和的值是多少。
上例中能得到的最大的和为3 + 7 + 4 + 9 = 23.
第一行，一个自然数T，表示总共给出的三角形数，对于每一个三角形，首先给出一个自然数n，表示将输入的三角形有n行。接下来有n行，第i行有2i-1个数字，
对于每个三角形，输出一个数，即能得到的最大的和。
2
2
1
1 2 3
4
3
7 1 4
2 4 3 6 2
8 5 2 9 3 6 2
-
4
-
23
代码：
-
#include<iostream>
-
#include<algorithm>
-
using namespace std;
-
-
int n,num[111][222], ans[111][222];
-
-
int dp(int i, int j)
-
{
-
if (ans[i][j])return ans[i][j];
-
if (i == n)return num[i][j];
-
int r = max(dp(i + 1, j), max(dp(i + 1, j + 1), dp(i + 1, j + 2)));
-
ans[i][j] = r + num[i][j];
-
return ans[i][j];
-
}
-
-
int main()
-
{
-
int t;
-
cin >> t;
-
while (t--)
-
{
-
cin >> n;
-
for (int i = 1; i <= n; i++)for (int j = 1; j <= i * 2 - 1; j++)
-
{
-
cin >> num[i][j];
-
ans[i][j] = 0;
-
}
-
cout << dp(1, 1) << endl;
-
}
-
return 0;
-
}
SCU 1114 数字三角
题目：
Description
下图是个数字三角，请编写一个程序计算从顶部至底部某处一条路径，使得该路径所经过的数字总和最大。
7
3 8
8 1 0
2 7 4 4
1． 每一步可沿左斜线向下或右斜线向下走；
2． 1<=三角形行数<=100
3． 三角形中的数字为整数 0，1，……，99。
4． 如果有多种情况结果都最大，任意输出一种即可。
输入：
第一行一个整数N，代表三角形的行数。
接下来N行，描述了一个数字三角。
输出：
第一行一个整数，代表路径所经过底数字总和。
第二行N个数，代表所经过的数字。
样例：
输入：
4
7
3 8
8 1 0
2 7 4 4
输出：
25
7 3 8 7
代码：
-
#include<iostream>
-
#include<string.h>
-
#include<stack>
-
using namespace std;
-
-
-
int main()
-
{
-
int n;
-
cin >> n;
-
int list[101][101];
-
memset(list, 0, sizeof(list));
-
cin >> list[1][1];
-
for (int i = 2; i <= n; i++)
-
{
-
for (int j = 1; j <= i; j++)
-
{
-
cin >> list[i][j];
-
list[i][j] += (list[i - 1][j] > list[i - 1][j - 1]) ? list[i - 1][j] : list[i - 1][j - 1];
-
}
-
}
-
int max = 0, key = 0;
-
for (int j = 1; j <= n; j++)
-
{
-
if (max < list[n][j])
-
{
-
max = list[n][j];
-
key = j;
-
}
-
}
-
cout << max << endl;
-
stack<int>s;
-
for (int i = n; i>0; i--)
-
{
-
if (list[i - 1][key] > list[i - 1][key - 1])
-
s.push(list[i][key] - list[i - 1][key]);
-
else s.push(list[i][key] - list[i-1][(key--)-1]);
-
}
-
while (!s.empty())
-
{
-
cout << s.top()<<" ";
-
s.pop();
-
}
-
return 0;
-
}
HDU - 2032 杨辉三角
题目：
还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Input输入数据包含多个测试实例，每个测试实例的输入只包含一个正整数n（1<=n<=30），表示将要输出的杨辉三角的层数。Output对应于每一个输入，请输出相应层数的杨辉三角，每一层的整数之间用一个空格隔开，每一个杨辉三角后面加一个空行。Sample Input
2 3
Sample Output
-
1
-
1 1
-
-
1
-
1 1
-
1 2 1
思路：
动态规划
和0-1背包差不多，可以使用空间压缩
代码：
-
#include<iostream>
-
using namespace std;
-
-
int main()
-
{
-
int n, ans[40];
-
while (cin >> n)
-
{
-
for (int i = 0; i <= n; i++)ans[i] = 0;
-
ans[1] = 1;
-
for (int r = 1; r <= n; r++)
-
{
-
cout << 1;
-
for (int i = r; i > 0; i--)ans[i] += ans[i - 1];
-
for (int i = 2; i <= r; i++)cout << " " << ans[i];
-
cout << endl;
-
}
-
cout << endl;
-
}
-
return 0;
-
}
CSU 1010: Water Drinking
题目：
Description
The Happy Desert is full of sands. There is only a kind of animal called camel living on the Happy Desert. Cause they live here, they need water here. Fortunately, they find a pond which is full of water in the east corner of the desert. Though small, but enough. However, they still need to stand in lines to drink the water in the pond.
Now we mark the pond with number 0, and each of the camels with a specific number, starting from 1. And we use a pair of number to show the two adjacent camels, in which the former number is closer to the pond. There may be more than one lines starting from the pond and ending in a certain camel, but each line is always straight and has no forks.
Input
There’re multiple test cases. In each case, there is a number N (1≤N≤100000) followed by N lines of number pairs presenting the proximate two camels. There are 99999 camels at most.
Output
For each test case, output the camel’s number who is standing in the last position of its line but is closest to the pond. If there are more than one answer, output the one with the minimal number.
Sample Input
1
0 1
5
0 2
0 1
1 4
2 3
3 5
5
1 3
0 2
0 1
0 4
4 5
Sample Output
1
4
2
题意：
给出一棵树，找出深度最小的叶子节点，
如果有多个这样的叶子节点，输出编号最小的那个。
直接用静态链表建立树，再用DP求出每个节点的深度即可。
代码：
-
#include<iostream>
-
#include<stdio.h>
-
using namespace std;
-
-
int fa[100005], deep[100005], isfa[100005];
-
-
int getdeep(int k)
-
{
-
if (deep[k])return deep[k];
-
int d = getdeep(fa[k]);
-
deep[k] = d + 1;
-
return deep[k];
-
}
-
-
int main()
-
{
-
int n, a, b;
-
while (scanf("%d", &n)!=EOF)
-
{
-
for (int i = 0; i <= n; i++)isfa[i] = 0;
-
for (int i = 0; i < n; i++)
-
{
-
scanf("%d%d", &a, &b);
-
fa[b] = a, isfa[a] = 1;
-
}
-
for (int i = 0; i <= n; i++)deep[i] = 0;
-
deep[0] = 1;
-
for (int i = 0; i <= n; i++)getdeep(i);
-
int minn = 100005;
-
for (int i = 1; i <= n; i++)if (isfa[i] == 0 && minn > deep[i])minn = deep[i];
-
for (int i = 1; i <= n; i++)if (isfa[i] == 0 && minn == deep[i])
-
{
-
printf("%d\n", i);
-
break;
-
}
-
}
-
return 0;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/113070354
- 点赞
- 收藏
- 关注作者
评论（0）