Div3专题
DFS/BFS专题（以前练过，应该不会写题解了）
DP专题

# Div3专题

E - Cake

2 3

4

## K.01背包

K - I NEED A OFFER!

Speakless很早就想出国，现在他已经考完了所有需要的考试，准备了所有要准备的材料，于是，便需要去申请学校了。要申请国外的任何大学，你都要交纳一定的申请费用，这可是很惊人的。Speakless没有多少钱，总共只攒了n万美元。他将在m个学校中选择若干的（当然要在他的经济承受范围内）。每个学校都有不同的申请费用a（万美元），并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”，他大叫一声。帮帮这个可怜的人吧，帮助他计算一下，他可以收到至少一份offer的最大概率。（如果Speakless选择了多个学校，得到任意一个学校的offer都可以）。

10 3

4 0.1

4 0.2

5 0.3

0 0

44.0%

01背包问题。因为至少得到一份offer的概率不能累计，所以将输入中得到offer的概率改为得不到offer的概率存储，然后建立dp数组。定义dp[i]为申请完第0 ~ i 个学校得不到offer的最小概率。则得到状态转移方程：

.其中a[i]是第i个学校的申请费用，b[i]是第i个学校不被录取的概率。（完全就是背包问题嘛）

## O.高精

O - N!

==贴这题只是想提醒一下自己，高精不一定非得写板子写类啊，这题直接用数组作乘法就ok了，不需要额外的对象化。==

## V.树的遍历

V - Binary Tree Traversals

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.

In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.

In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.

In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.

Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.

The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.

For each test case print a single line specifying the corresponding postorder sequence.

9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6

7 4 2 8 9 5 6 3 1

## W.思维

Friend number are defined recursively as follows.
(1) numbers 1 and 2 are friend number;
(2) if a and b are friend numbers, so is ab+a+b;
(3) only the numbers defined in (1) and (2) are friend number.
Now your task is to judge whether an integer is a friend number.

There are several lines in input, each line has a nunnegative integer a, 0<=a<=2^30.

For the number a on each line of the input, if a is a friend number, output “YES!”, otherwise output “NO!”.

3

13121

12131

YES!

YES!

NO!

# DP专题

## A.前缀 + dp

A题链接

Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S1, S2, S3, S4 … Sx, … Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + … + Sj (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + … + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).

But Im lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 … Sn.
Process to the end of file.

Output the maximal summation described above in one line.

1 3 1 2 3

2 6 -1 4 -2 3 -2 3

6

8

^fdp是我瞎取的名字啦^

## C.排序 + DP

C题链接

A group of researchers are designing an experiment to test the IQ of a monkey. They will hang a banana at the roof of a building, and at the mean time, provide the monkey with some blocks. If the monkey is clever enough, it shall be able to reach the banana by placing one block on the top another to build a tower and climb up to get its favorite food.

The researchers have n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions (xi, yi, zi). A block could be reoriented so that any two of its three dimensions determined the dimensions of the base and the other dimension was the height.

They want to make sure that the tallest tower possible by stacking blocks can reach the roof. The problem is that, in building a tower, one block could only be placed on top of another block as long as the two base dimensions of the upper block were both strictly smaller than the corresponding base dimensions of the lower block because there has to be some space for the monkey to step on. This meant, for example, that blocks oriented to have equal-sized bases couldn’t be stacked.

Your job is to write a program that determines the height of the tallest tower the monkey can build with a given set of blocks.

The input file will contain one or more test cases. The first line of each test case contains an integer n,
representing the number of different blocks in the following data set. The maximum value for n is 30.
Each of the next n lines contains three integers representing the values xi, yi and zi.
Input is terminated by a value of zero (0) for n.

For each test case, print one line containing the case number (they are numbered sequentially starting from 1) and the height of the tallest possible tower in the format “Case case: maximum height = height”.

Sample Input

1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0

Sample Output

Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342

J题链接

## L.最大公共子序列

（以后题解的题面就直接复制OJ上的吧，自己打题面的格式没啥意义哈哈哈）

description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, …, xm > another sequence Z = < z1, z2, …, zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, …, ik > of indices of X such that for all j = 1,2,…,k, xij = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

Sample Output

## Q.二维DP

description

Today is army day, but the servicemen are busy with the phalanx for the celebration of the 60th anniversary of the PRC.
A phalanx is a matrix of size nn, each element is a character (a~z or A~Z), standing for the military branch of the servicemen on that position.
For some special requirement it has to find out the size of the max symmetrical sub-array. And with no doubt, the Central Military Committee gave this task to ALPCs.
A symmetrical matrix is such a matrix that it is symmetrical by the “left-down to right-up” line. The element on the corresponding place should be the same. For example, here is a 3
3 symmetrical matrix:
cbx
cpb
zcc

Input

There are several test cases in the input file. Each case starts with an integer n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.

Output

Each test case output one line, the size of the maximum symmetrical sub- matrix.

Sample Input

Sample Output

dp[i][j]表示a[i][j]为某个对称方阵左下角的字符时最大对称子方阵的大小。由于自己肯定是个对称方阵，初始化所有的dp[i][j]为1.