hdu1024

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1024

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#define FI(a, b, c) for(int a = (b); a <= (c); a++)
#define FD(a, b, c) for(int a = (b); a >= (c); a--)
using namespace std;

int n, m, t;
long long d[1000005], l[1000005];

int main(){
while(scanf("%d %d", &m, &n) != EOF){
FI(i, 1, m) d[i] = l[i] = -1e15;

while(n--){
scanf("%d", &t);
FD(i, m, 1){
d[i] = max(d[i], l[i - 1]) + t;
l[i] = max(l[i], d[i]);
}
}
printf("%lld\n", l[m]);
}
}

高度为h的AVL树的最少节点数

设高度为h的AVL树最少的节点数为f(h)
可以算出f(0)=0,f(1)=1,f(2)=2.
设左子树的高度为h-1,则右子树的高度为h-2.
因此得到递推公式:f(h) = f(h-1) + f(h-2) + 1.

Hash

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment