Description

The world financial crisis is quite a subject. Some people are more relaxed while others are quite anxious. John is one of them. He is very concerned about the evolution of the stock exchange. He follows stock prices every day looking for rising trends. Given a sequence of numbers p1, p2,…,pn representing stock prices, a rising trend is a subsequence pi1 < pi2 < … < pik, with i1 < i2 < … < ik. John’s problem is to find very quickly the longest rising trend.

Input

Each data set in the file stands for a particular set of stock prices. A data set starts with the length L (L ≤ 100000) of the sequence of numbers, followed by the numbers (a number fits a long integer). White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

Output

The program prints the length of the longest rising trend. For each set of data the program prints the result to the standard output from the beginning of a line.

Sample Input

1
2
3
4
5
6

6 
5 2 1 4 5 3 
3  
1 1 1 
4 
4 3 2 1

Sample Output

1
2
3

3 
1 
1

霍夫曼树的定义、实现及霍夫曼编码的求解与输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;

struct HTNode {
	int weight;//权值
	int parent;//指向父结点的指针域
	int lchild;//左指针域
	int rchild;//右指针域
};

class huffman_BT {
private:
	HTNode *bt;
	char **hc;
	int nn;
public:
	void select(HTNode *p, int k, int *i, int *j);
	void creat_hufm_BT();
	int HuffmanCoding();
	void HuffmanDisplay();
};
//在前k-1个结点中选择权值最小的两个结点i和j
void huffman_BT::select(HTNode *p, int k, int *i, int *j) {
	int w, n = 0;
	while (n < k && (p + n)->parent != -1) n++;//寻找指向父结点指针为空的起始结点
	w = (p + n)->weight;
	*i = n;
	while (n < k) {
		if ((((p + n)->weight) < w) && ((p + n)->parent == -1)) *i = n, w = (p + n)->weight;
		n++;
	}
	n = 0;
	while ((n < k) && ((p + n)->parent != -1) || (n == (*i))) n++;
	w = (p + n)->weight;
	*j = n;
	while (n < k) {
		if (((p + n)->weight < w) && (n != (*i)) && ((p + n)->parent == -1)) {
			*j = n;
			w = (p + n)->weight;
		}
		n++;
	}
	if ((*i) < (*j)) n = (*i), *i = *j, *j = n;
}

void huffman_BT::creat_hufm_BT() {
	HTNode *p;
	int k, i, j, m;
	cout << "请输入结点的个数：";
	cin >> nn;
	m = nn * 2 - 1;
	bt = new HTNode[m];
	p = bt;
	for (i = 0; i < m; i++) {
		p[i].weight = 0;
		p[i].parent = -1;
		p[i].lchild = -1;
		p[i].rchild = -1;
	}
	cout << "请依次输入权值：" << endl;
	for (i = 0; i < nn; i++) {
		cout << "请输入第" << i + 1 << "个权值：";
		cin >> p[i].weight;
	}
	for (k = nn; k < m; k++) {
		select(p, k, &i, &j);
		(p + i)->parent = k;
		(p + j)->parent = k;
		(p + k)->lchild = i;
		(p + k)->rchild = j;
		(p + k)->weight = (p + i)->weight + (p + j)->weight;
	}
}
//从叶子到根逆向求每个字符的霍夫曼编码
int huffman_BT::HuffmanCoding() {
	char *cd = new char[nn];
	int start, c, f;
	hc = new char*[nn];
	cd[nn - 1] = '\0';
	for (int i = 0; i < nn; i++) {
		start = nn - 1;
		for (c = i, f = bt[i].parent; f != -1; c = f, f = bt[f].parent) {
			if (bt[f].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		hc[i] = new char[nn - start];
		strcpy(hc[i], &cd[start]);
	}
	return 1;
}
//霍夫曼编码信息输出
void huffman_BT::HuffmanDisplay() {
	HTNode *p;
	int k;
	p = bt;
	cout << "k" << setw(7) << "weight" << setw(7) << "parent" << setw(7) << "lchild" << setw(7) << "rchild" << endl;
	for (k = 0; k < 2 * nn - 1; k++) {
		cout << k << setw(7) << (p + k)->weight << setw(7) << (p + k)->parent << setw(7) << (p + k)->lchild << setw(7) << (p + k)->rchild << endl;
	}
	cout << "霍夫曼编码为：" << endl;
	for (k = 0; k < nn; k++) {
		cout << char('A' + k) << "(权值：" << p[k].weight << "):" << hc[k] << endl;
	}
}

int main() {
	huffman_BT hbt;
	hbt.creat_hufm_BT();
	hbt.HuffmanCoding();
	hbt.HuffmanDisplay();
	return 0;
}

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

1
2
3

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

1
2
3

4
2
0

二叉树的定义、实现、遍历、输出、应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

struct BiTNode {
	int data;
	BiTNode *lchild;
	BiTNode *rchild;
};

class BinaryTree {
private:
	BiTNode *bt;
	int RCreate(BiTNode *p, int k, int end);
public:
	void CreateBiTree(int end);
	BinaryTree() { bt = NULL; }
	void Release(BiTNode *root);
	~BinaryTree();
	int PreTraverse(BiTNode *p);
	int InTraverse(BiTNode *p);
	int PostTraverse(BiTNode *p);
	void PreOrderTraverse();
	void InOrderTraverse();
	void PostOrderTraverse();
	void LevelOrderTraverse();
	void LeafCount();
	void BiTreeDepth();
	BiTNode *GetTreeNode(int item, BiTNode *lptr, BiTNode *rptr);
	BiTNode *CopyTree(BiTNode *p);
	int CompareTree(BiTNode *t1, BiTNode *t2);
	BiTNode *GetRoot();
	void BiTreeDisplay(BiTNode *bt, int level = 1);
};
//创建二叉树递归函数
int BinaryTree::RCreate(BiTNode * p, int k, int end) {
	BiTNode *q;
	int e;
	cin >> e;
	if (e != end) {
		q = new BiTNode;
		q->data = e;
		q->lchild = NULL;
		q->rchild = NULL;
		if (k == 1) p->lchild = q;
		if (k == 2) p->rchild = q;
		RCreate(q, 1, end);
		RCreate(q, 2, end);
	}
	return 0;
}
//按先序序列创建二叉树
void BinaryTree::CreateBiTree(int end) {
	cout << "请按先序序列的顺序输入二叉树，0为空指针域标志：" << endl;
	BiTNode *p;
	int e;
	cin >> e;
	if (e == end) return;
	p = new BiTNode;
	if (!p) {
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;
	bt = p;
	RCreate(p, 1, end);
	RCreate(p, 2, end);
}
//先序遍历递归函数
int BinaryTree::PreTraverse(BiTNode *p) {
	if (p != NULL) {
		cout << p->data << ' ';
		PreTraverse(p->lchild);
		PreTraverse(p->rchild);
	}
	return 0;
}
//中序遍历递归函数
int BinaryTree::InTraverse(BiTNode *p) {
	if (p != NULL) {
		InTraverse(p->lchild);
		cout << p->data << ' ';
		InTraverse(p->rchild);
	}
	return 0;
}
//后续遍历递归函数
int BinaryTree::PostTraverse(BiTNode * p) {
	if (p != NULL) {
		PostTraverse(p->lchild);
		PostTraverse(p->rchild);
		cout << p->data << ' ';
	}
	return 0;
}
//销毁二叉树递归函数
void BinaryTree::Release(BiTNode *root) {
	if (root != NULL) {
		Release(root->lchild);
		Release(root->rchild);
		delete root;
	}
}
//析构函数
BinaryTree::~BinaryTree() {
	Release(bt);
}
//非递归先序遍历二叉树
void BinaryTree::PreOrderTraverse() {
	cout << "先序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode> s;
	while (p || !s.empty()) {
		if (p) {
			cout << p->data << ' ';
			s.push(*p);
			p = p->lchild;
		}
		else {
			p = new BiTNode;
			*p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}
//非递归中序遍历二叉树
void BinaryTree::InOrderTraverse() {
	cout << "中序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode> s;
	while (p || !s.empty()) {
		if (p) {
			s.push(*p);
			p = p->lchild;
		}
		else {
			p = new BiTNode;
			*p = s.top();
			s.pop();
			cout << p->data << ' ';
			p = p->rchild;
		}
	}
	cout << endl;
}
//非递归后序遍历结点类型
struct BiTNode1 {
	BiTNode *bt;
	int tag;
};
//非递归后序遍历二叉树
void BinaryTree::PostOrderTraverse() {
	cout << "后序（非递归）遍历二叉树：";
	BiTNode *p = bt;
	stack<BiTNode1> s;
	BiTNode1 *temp;
	while (p || !s.empty()) {
		if (p) {
			BiTNode1 *t = new BiTNode1;
			t->bt = p;
			t->tag = 1;
			s.push(*t);
			p = p->lchild;
		}
		else {
			temp = new BiTNode1;
			*temp = s.top();
			s.pop();
			if (temp->tag == 1) {
				temp->tag = 2;
				s.push(*temp);
				p = new BiTNode;
				p = temp->bt->rchild;
			}
			else {
				cout << temp->bt->data << ' ';
				p = NULL;
			}
		}
	}
	cout << endl;
}
//层次遍历二叉树
void BinaryTree::LevelOrderTraverse() {
	cout << "层次遍历二叉树：";
	queue<BiTNode> q;
	BiTNode *t;
	if (bt) {
		q.push(*bt);
		while (!q.empty()) {
			t = new BiTNode;
			*t = q.front();
			q.pop();
			if (t) cout << t->data << ' ';
			if (t->lchild) q.push(*t->lchild);
			if (t->rchild) q.push(*t->rchild);
		}
	}
	cout << endl;
}
//计算叶子的个数递归函数
void Leaf(BiTNode *p, int &count) {
	if (p) {
		Leaf(p->lchild, count);
		Leaf(p->rchild, count);
		if (p->lchild == NULL && p->rchild == NULL) count++;
	}
}
//后序遍历计算叶子的个数
void BinaryTree::LeafCount() {
	int count = 0;
	Leaf(bt, count);
	cout << "叶子的个数为" << count << endl;
}
//计算深度递归函数
void Depth(BiTNode *p, int level, int &depth) {
	if (p->lchild) Depth(p->lchild, level + 1, depth);
	if (p->rchild) Depth(p->rchild, level + 1, depth);
	if (level > depth) depth = level;
}
//后序遍历计算深度
void BinaryTree::BiTreeDepth() {
	int depth = 0;
	if (bt) {
		Depth(bt, 1, depth);
	}
	cout << "二叉树的深度为" << depth << endl;
}
//获取二叉树的一个结点
BiTNode *BinaryTree::GetTreeNode(int item, BiTNode * lptr, BiTNode * rptr) {
	BiTNode *p = new BiTNode;
	p->data = item;
	p->lchild = lptr;
	p->rchild = rptr;
	return p;
}
//先序遍历复制一棵二叉树
BiTNode *BinaryTree::CopyTree(BiTNode *p) {
	BiTNode *newlptr, *newrptr;
	if (p == NULL) return NULL;
	if (p->lchild) newlptr = CopyTree(p->lchild);
	else newlptr = NULL;
	if (p->rchild) newrptr = CopyTree(p->rchild);
	else newrptr = NULL;
	bt = GetTreeNode(p->data, newlptr, newrptr);
}
//先序遍历判断两棵二叉树是否相等
int BinaryTree::CompareTree(BiTNode * t1, BiTNode * t2) {
	if (t1 == NULL && t2 == NULL) return 1;
	else if (t1->data == t2->data&&CompareTree(t1->lchild, t2->lchild) && CompareTree(t1->rchild, t2->rchild)) return 1;
	else return 0;
}
//获取根结点
BiTNode* BinaryTree::GetRoot() {
	if (bt != NULL) return bt;
	return NULL;
}
//反中序递归横向树状显示一棵二叉树
void BinaryTree::BiTreeDisplay(BiTNode * bt, int level) {
	if (bt) {
		BiTreeDisplay(bt->rchild, level + 1);
		for (int i = 0; i < level; i++) cout << "  ";
		cout << bt->data << endl;
		BiTreeDisplay(bt->lchild, level + 1);
	}
}

int main() {
	BinaryTree bit;
	BinaryTree bit1;
	while (1) {
		bit.CreateBiTree(0);
		bit.BiTreeDisplay(bit.GetRoot(),0);

		cout << "先序（递归）遍历二叉树：";
		bit.PreTraverse(bit.GetRoot());
		cout << endl;

		cout << "中序（递归）遍历二叉树：";
		bit.InTraverse(bit.GetRoot());
		cout << endl;

		cout << "后序（递归）遍历二叉树：";
		bit.PostTraverse(bit.GetRoot());
		cout << endl;

		bit.PreOrderTraverse();
		bit.InOrderTraverse();
		bit.PostOrderTraverse();
		bit.LevelOrderTraverse();

		bit.LeafCount();
		bit.BiTreeDepth();

		bit1.CopyTree(bit.GetRoot());
		bit1.BiTreeDisplay(bit1.GetRoot(), 0);
		if (bit1.CompareTree(bit.GetRoot(), bit1.GetRoot())) cout << "相等，拷贝成功" << endl;
		cout << endl;
	}
	return 0;
}

Description

The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the move player takes one card out of the row and scores the number of points equal to the product of the number on the card taken and the numbers on the cards on the left and on the right of it. It is not allowed to take out the first and the last card in the row. After the final move, only two cards are left in the row. The goal is to take cards in such order as to minimize the total number of scored points. For example, if cards in the row contain numbers 10 1 50 20 5, player might take a card with 1, then 20 and 50, scoring $10150 + 50205 + 10505 = 500+5000+2500 = 8000 $.If he would take the cards in the opposite order, i.e. 50, then 20, then 1, the score would be $15020 + 1205 + 1015 = 1000+100+50 = 1150$.

Input

The first line of the input contains the number of cards $N (3 \leq N \leq 100)$. The second line contains N integers in the range from 1 to 100, separated by spaces.

Output

Output must contain a single integer - the minimal score.

Sample Input

1
2

6
10 1 50 50 20 5

Sample Output

1

3650

Description

Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a ‘desirability’ factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input

* Line 1: Two space-separated integers: N and M Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di*

Output

* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints

Sample Input

1
2
3
4
5

4 6
1 4
2 6
3 12
2 7

Sample Output

1

23

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d. We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

​ Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases. The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. “-1” installation means no solution for that case.

Sample Input

1
2
3
4
5
6
7
8
9

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

1
2

Case 1: 2
Case 2: 1

Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too.FJ sadly realizes that he doesn’t own a saw with which to cut the wood, so he mosies over to Farmer Don’s Farm with this long board and politely asks if he may borrow a saw.Farmer Don, a closet capitalist, doesn’t lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

Input

Line 1: One integer N, the number of planks Lines 2..N+1: Each line contains a single integer describing the length of a needed plank

Output

Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts

Sample Input

1
2
3
4

3
8
5
8

Sample Output

1

34

Description

Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.

Input

The input test file will contain multiple cases. Each test case begins with a single line containing an integer R, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integer n, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positions x1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case with R = n = −1.

Output

For each test case, print a single integer indicating the minimum number of palantirs needed.

Sample Input

1
2
3
4
5

0 3
10 20 20
10 7
70 30 1 7 15 20 50
-1 -1

Sample Output

1
2

2
4

Description

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual”Farmer of the Year” competition. In this contest every farmer arranges his cows in a line and herds them past the judges.The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows’ names.FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he’s finished, FJ takes his cows for registration in this new order.Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

* Line 1: A single integer: N Lines 2..N+1: Line i+1 contains a single initial (‘A’..’Z’) of the cow in the i*th position in the original line

Output

The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows (‘A’..’Z’) in the new line.

Sample Input

1
2
3
4
5
6
7

6
A
C
D
B
C
B

Sample Output

1

ABCBCD