A - 递归的函数
Description
给定一个函数 f(a, b, c)：
如果 a ≤ 0 或 b ≤ 0 或 c ≤ 0 返回值为 1；
如果 a > 20 或 b > 20 或 c > 20 返回值为 f(20, 20, 20)；
如果 a < b 并且 b < c 返回 f(a, b, c?1) + f(a, b?1, c?1) ? f(a, b?1, c)；
其它情况返回 f(a?1, b, c) + f(a?1, b?1, c) + f(a?1, b, c?1) ? f(a-1, b-1, c-1)。
看起来简单的一个函数？你能做对吗？
Input
输入包含多组测试数据，对于每组测试数据：
输入只有一行为 3 个整数a, b, c(a, b, c < 30)。
Output
对于每组测试数据，输出函数的计算结果。
Sample
Input
1 1 1 2 2 2
Output
2 4
Hint
#include<bits/stdc++.h>
using namespace std;
// **记录递归路径，每次不用从头递归
int m[30][30][30];
int f(int a, int b, int c)
{if(a <= 0 || b <= 0 || c <= 0){return 1;}if(m[a][b][c] > 0){return m[a][b][c];// 如果这个值被记录过，直接返回该值}// 与普通递归的区别所在else if(a > 20 || b > 20 || c > 20){return m[a][b][c] = f(20, 20, 20);}else if(a < b && b < c){return m[a][b][c] = f(a,b,c-1) + f(a,b-1,c-1) - f(a,b-1,c);}else{return m[a][b][c] = f(a-1,b,c) + f(a-1,b-1,c) + f(a-1,b,c-1) - f(a-1,b-1,c-1);}
}
int main()
{int a, b, c;while(cin >> a >> b >> c){cout << f(a, b, c) << endl;}system("pause");return 0;
}B - 数字三角形问题
Description
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。
Input
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。
Output
输出数据只有一个整数，表示计算出的最大值。
Sample
Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Output
30
Hint
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 1e5 + 100;
const int M = 2e2 + 100;
const int MAXN = 0x3f3f3f3f;
const ll LMANX = 0x3f3f3f3f3f3f3f3f;
#define PI 3.14159265358979323846
int a[M][M];
int maxn[M][M];
int main()
{int n;scanf("%d", &n);for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){scanf("%d", &a[i][j]);}}for(int j = 1; j <= n; j++)maxn[n][j] = a[n][j];// 最后一行的每个数先存进maxn[][]for(int i = n - 1; i >= 1; i--){// 这里就要从倒数第二行开始for(int j = 1; j <= i; j++){maxn[i][j] = max(maxn[i+1][j], maxn[i+1][j+1]) + a[i][j];}// 最后一行的每个数和该数后一个数中较大的那个加上上一行的数// 遍历完最后一行后，所有的maxn[][]也成为了一行数，循环向上遍历每行}printf("%d", maxn[1][1]);// 最后剩下的maxn[1][1]就是最大der~return 0;
}E - 最长上升子序列
Description
一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1<= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。
你的任务，就是对于给定的序列，求出最长上升子序列的长度。
Input
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
Output
最长上升子序列的长度。
Sample
Input
7 1 7 3 5 9 4 8
Output
4
//E - 最长上升子序列
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], f[N];
int main()
{int n, i, j;cin >> n;for(i = 0; i < n; i++){cin >> a[i];}int cnt = 0;for(i = 0; i < n; i++){f[i] = 1;// 只有一个数时最长上升子序列的长度就是 1for(j = i; j >= 0; j--){// 这里的意思是 j == i - 1if(a[j] < a[i]){f[i] = max(f[i], f[j]+1);}// 不懂}cnt = max(f[i], cnt);}cout << cnt;system("pause");return 0;
}