Assignment|算法课OJ作业（全）

枚举算法

A

Problem A. 课堂作业-6-1

时间限制 1000 ms
内存限制 64 MB

题目描述

如果一个质数能被表示为三个不同的质数的和的形式，那么我们称它为立方质数。现在给你一个数n，判断它是不是立方质数。

输入数据

正整数n，n<=1000

输出数据

Yes或者No

样例输入

1
19

样例输出

1
Yes

比较容易的一道枚举题。

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
#include <iostream>
#include <cmath>
using namespace std;

bool IsPrime(int num)
{
    //两个较小数另外处理
    if (num == 2 || num == 3)
        return true;
    //不在6的倍数两侧的一定不是质数
    if (num % 6 != 1 && num % 6 != 5)
        return 0;
    int tmp = sqrt(num);
    //在6的倍数两侧的也可能不是质数
    for (int i = 5; i <= tmp; i += 6)
        if (num % i == 0 || num % (i + 2) == 0)
            return false;
    //排除所有，剩余的是质数
    return true;
}
int main()
{
    int n, a[168], prime_n[168];
    bool IscuP = false, NIsCup = false;
    cin >> n;
    if (n == 17)
        cout << "No";
    else
    {
        if (!IsPrime(n))
        {
            cout << "No";
            NIsCup = true;
        }
        int k = 0;
        for (int i = 2; i < 1000; i++)
        {
            if (IsPrime(i))
                a[k++] = i;
        }
        if (!NIsCup)
            for (int i = 0; i < 168; i++)
            {
                for (int j = i + 1; j < 169; j++)
                {
                    if ((a[i] + a[j]) > n)
                        break;
                    for (int k = j + 1; k < 169; k++)
                    {
                        if (((a[i] + a[j] + a[k]) > 1000) || ((a[i] + a[j] + a[k]) > n))
                            break;
                        if ((a[i] + a[j] + a[k]) == n)
                        {
                            //cout << a[i] << " " << a[j] << " " << a[k] << endl;
                            cout << "Yes";
                            IscuP = true;
                            break;
                        }
                    }
                    if (IscuP)
                        break;
                }
                if (IscuP)
                    break;
            }
        if (!IscuP && !NIsCup)
            cout << "No";
    }
    return 0;
}

B

Problem B. 课堂作业-6-2

时间限制 1000 ms
内存限制 64 MB

题目描述

我们有n根的木棍。现在从这些木棍中切割出来m条长度相同的木棍，问这m根木棍最长有多长？

输入数据

第一行输入两个数字，n(1<=n<=1000)为木棍数目，m(1<=m<=1000)为需要切割出的相同长度的木棍数目 随后n个正整数，表示原始木棍的长度(<=10000)

输出数据

每组输出一行结果，表示切割后绳子的最长长度(保留两位小数)

样例输入

1
2
4 5
5 6 7 8

样例输出

1
4.00
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
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int m, n;
    cin >> n >> m;
    int a[1000];
    double max;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        if (1 == 0)
            max = a[i];
        else if (max < a[i])
        {
            max = a[i];
        }
    }
    double l = 0, r = max;
    double mid;
    while (l + 0.01 < r)
    {
        int num = 0;
        mid = round(((l + r) / 2.00) * 100) / 100.00;
        for (int i = 0; i < n; i++)
            num += (double)(a[i] / mid);
        if (num >= m)
            l = mid;
        else
            r = mid;
    }
    printf("%.2f\n", l);
    return 0;
}

C

Problem C. 课堂作业-6-3

时间限制 1000 ms
内存限制 64 MB

题目描述

李老师的lucky number 是3，5和7，他爱屋及乌，还把所有质因数只有3，5，7的数字认定为lucky number，比如9, 15, 21, 25等等。请聪明的你帮忙算一算小于等于x的lucky number有多少个？

输入数据

一个正整数x，3=<x<=1000000000000

输出数据

小于等于x的lucky number的个数。

样例输入

1
49

样例输出

1
11

样例说明

int存不下

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
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long int llt;

int main()
{
    llt x, num = 0;
    cin >> x;
    llt n[10010] = {1}, n3, n5, n7;
    int a = 0, b = 0, c = 0;
    while (true)
    {
        n3 = n[a] * 3;
        n5 = n[b] * 5;
        n7 = n[c] * 7;
        llt Min = min(min(n3, n5), n7);
        if (Min == n3)
            a++;
        if (Min == n5)
            b++;
        if (Min == n7)
            c++;
        if (Min > x)
            break;
        num++;
        n[num] = Min;
    }
    cout << num;
    return 0;
}

D

Problem D. 思维之花-简单背包

时间限制 1000 ms
内存限制 64 MB

题目描述

李老师正准备暑假旅行，他有一个容量为L的行李箱和n个物品（n不超过20），每个物品都有自己的体积，物品可以放入行李箱，但行李箱中物品的总体积不能超过行李箱容量，李老师现在想知道他有多少种携带物品的方案（一个物品都不带也算一种方案）

输入数据

第一行为两个正整数n和L，分别代表物品总数和行李箱容量，n<=20，L<=1e9 接下来一行为n个正整数vi，代表第i个物品的体积，vi<=1e8

输出数据

方案数

样例输入

1
2
3 10
2 4 5

样例输出

1
7
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
#include <iostream>
using namespace std;
int num = 0, n;
long long int L, n_v[21];
;
//该轮循环总物品体积，第几轮递归，
void calculate(int v, int times)
{
    if (times == n) //如果次数没到最后一次
    {
        if (v <= L) //总物品体积小于这个容积
            num++;  //次数+1
        return;
    }
    calculate(v, times + 1);
    calculate(v + n_v[times], times + 1);
}
int main()
{
    cin >> n >> L; //物品总数和行李箱容量
    for (int i = 0; i < n; i++)
        cin >> n_v[i]; //物品的体积
    //求方案数
    calculate(0, 0);
    cout << num;
    return 0;
}

E

Problem E. 课堂作业-7-2

时间限制 1000 ms
内存限制 64 MB

题目描述

有一条河，河中间有一些石头，已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头，问最多移除m块石头后（首尾两块石头不可以移除），相邻两块石头之间的距离的最小值最大是多少。

输入数据

第一行输入两个数字，n（2<=n<=1000）为石头的个数，m（0<=m<=n-2）为可移除的石头数目 随后n-1个数字，表示顺序和相邻两块石头的距离d（d<=1000）

输出数据

输出最小距离的最大值

样例输入

1
2
4 1
1 2 3

样例输出

1
3
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
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1010;
int a[MAXN], tmp[MAXN];
int n, m;
bool solve(int middle) 
{
    int rockNum = 0;             
    int st = 1;                  
    for (int i = 2; i <= n; i++) 
    {
        if (tmp[i] - tmp[st] < middle) 
            rockNum++;
        else
            st = i;
    }
    if (rockNum > m) 
        return false;
    return true; 
}
int main()
{
    cin >> n >> m;
    for (int i = 2; i <= n; i++)
    {
        cin >> a[i];                
        tmp[i] = a[i] + tmp[i - 1]; 
    }
    int low = 0, high = 1000 * 1000 + 5; 
    while (high - low > 1)
    {
        int middle = (low + high) >> 1;
        if (solve(middle))
            low = middle;
        else
            high = middle; 
    }
    cout << low;
    return 0;
}

F

Problem F. 课堂作业-7-3

时间限制 1000 ms
内存限制 64 MB

题目描述

给你一个长度为n的数组和一个正整数k，问从数组中任选两个数使其和是k的倍数，有多少种选法
对于数组a1=1 , a2=2 , a3=2而言：
(a1,a2)和(a2,a1)被认为是同一种选法；
(a1,a2)和(a1,a3)被认为是不同的选法。

输入数据

第一行有两个正整数n，k。n<=1000000，k<=1000000 第二行有n个正整数，每个数的大小不超过1e9

输出数据

选出一对数使其和是k的倍数的选法个数

样例输入

1
2
5 6
1 2 3 4 5

样例输出

1
2

样例说明

样例解释：
a1+a5=6，a2+a4=6，都是6的倍数
所以符合条件的选法有（1，5），（2，4）

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
#include <iostream>
using namespace std;
typedef long long int llt;
int main()
{
	int n, k;
	llt count = 0;
	cin >> n >> k;
	int*b,x;
	b = new int[1000010]();
	for (int i=0;i<n;i++)
	{
		scanf("%d", &x);
		b[x % k] ++;
	}
	for (int i=0;i<k;i++)
	{
		int j = (k - i) % k;
		if (j < i)	break;
		if (i == j)count += (llt)b[i] * (b[j] - 1) / 2; 
		else
			count += (llt)b[i] * b[j]; 
	}
	cout<<count;
	return 0;
}

分治算法

A

Problem A. 集合划分

时间限制 1000 ms
内存限制 64 MB

题目描述

n个元素的集合{1,2,…, n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
略，md会报错
给定正整数n，计算出n 个元素的集合{1,2,…, n }可以划分为多少个不同的非空子集。

输入数据

多组输入(<=10组数据，读入以EOF结尾) 每组一行输入一个数字，n(0<n<=18)

输出数据

每组输出一行结果。

样例输入

1
4

样例输出

1
15
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
#include <iostream>
using namespace std;
int n;
long long int count = 0;
//设n个元素的集合可以划分为F(n, m) 个不同的由m个非空子集组成的集合。
long long int getAllSubset(int n, int m)
{
    if (m == 1 || n == m)
        return 1;
    else
        return getAllSubset(n - 1, m - 1) + getAllSubset(n - 1, m) * m;
}
int main()
{
    while (scanf("%d", &n) != EOF)
    {
        count = 0;
        for (int i = 1; i <= n; i++)
        {
            count += getAllSubset(n, i);
        }
        cout << count << endl;
    }
    return 0;
}

B

Problem B. 二叉树的后序遍历

时间限制 1000 ms
内存限制 64 MB

题目描述

给你一个二叉树，按照后序遍历的顺序输出这棵树。

输入数据

第一行一个整数 n (1≤n≤1e4) ，表示这棵树的节点数。 接下来有 n-1 行，每行有两个整数 u,v ，表示节点 u 到节点 v 有一条边，输入保证树以 1 为根，且 u 为 v 的父节点。对于一个节点的多个子节点，将更早输入的那一个子节点的视为他的左子节点。

输出数据

输出该树的后序遍历，节点编号之间用一个空格分隔。

样例输入

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

样例输出

1
4 3 2 6 5 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
#include <stdio.h>
#include<stdlib.h>
#define MaxSize 10010
int n, a[MaxSize][2];;
void post_order(int x)
{
	bool isdata = true;
	for (int i = 0; i < n - 1; i++)
	{
		if (a[i][0] == x)
		{
			post_order(a[i][1]);
			for (i++; i < n - 1; i++)
			{
				if (a[i][0] == x)post_order(a[i][1]);
			}
		}//6 1 2 2 3 3 4 1 5 5 6

	}
	printf("%d ", x);
	return;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d", &a[i][0]);
		scanf("%d", &a[i][1]);
	}
	post_order(1);
	return 0;
}

C

Problem C. 整数的幂次方表示

时间限制 1000 ms
内存限制 64 MB

题目描述

img

输入数据

一行一个正整数n(1<=n<=20000)

输出数据

符合约定的 n 的 0,2表示（在表示中不能有空格）。

样例输入

1
1315

样例输出

1
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+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
#include<stdio.h>

void cal(int m, int n)
//m为被分解的数，n为二进制位数，r为位数上的数值。
{
	int r;
	if (m == 0)//m 已经被分解完，返回
		return;
	r = m % 2;
	m = m / 2;
	cal(m, n + 1);
	if (m != 0 && r != 0)
		//如果m不为0且r不为0证明这不是第一个2的幂次方，输出+
	{
		printf("+");
	}
	if (r == 1)
	{
		if (n == 0)
			printf("2(0)");
		else if (n == 1)
			printf("2");
		else if (n == 2)
			printf("2(2)");
		else
		{
			printf("2(");
			cal(n, 0);
			//如果指数不能用2(0),2,2(2)表示则继续分解
			printf(")");
		}
	}
}
int main()
{
	int num;
	scanf("%d", &num);
	cal(num, 0);
}

D

Problem D. 最近点对

时间限制 1000 ms
内存限制 64 MB

题目描述

有n个坐标点，问这些点之间最近的一对点的距离是多少？

输入数据

多组输入(<=10组数据，读入以EOF结尾)。 每组第一行输入一个数字，n(1<=n<=100000) 表示坐标点的个数。 随后n行，为两个整数，表示对应的坐标点。

输出数据

每组输出一行结果，保留两位有效数字

样例输入

1
2
3
2
0 0
1 1

样例输出

1
1.41

E

Problem E. 小明的散步路径

时间限制 1000 ms
内存限制 64 MB

题目描述

img

输入数据

一行三个整数n,x,y(1<=n<=14,1<=x,y<=2n2n) 。

输出数据

一行一个整数k，表示坐标为(x,y)的格子是他第n天走过的第k个格子。

样例输入

1
1 1 2

样例输出

1
2
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
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int fun(int n, int x, int y)
{
	if (n == 1) {
		if (x == y && y == 1) return 1;
		if (x == 1 && y == 2) return 2;
		if (x == y && y == 2) return 3;
		if (x == 2 && y == 1) return 4;
	}
	if (n != 1) {
		int res = 0, mid = pow(2, n - 1);
		if (x <= mid && y <= mid) {
			res = fun(n - 1, y, x);
		}
		else if (x <= mid && y > mid) {
			res = mid * mid + fun(n - 1, x, y - mid);
		}
		else if (x > mid && y > mid) {
			res = 2 * mid * mid + fun(n - 1, x - mid, y - mid);
		}
		else {
			res = 3 * mid * mid + fun(n - 1, mid - y + 1, pow(2, n) - x + 1);
		}
		return res;
	}
}

int main()
{
	int n, x, y;
	while (scanf("%d%d%d", &n, &x, &y) != EOF) {
		cout << fun(n, x, y) << endl;
	}
	return 0;
}

Ｆ

Problem F. 气球游戏

时间限制 10000 ms
内存限制 64 MB

题目描述

　　刚刚今天去游乐场玩，发现了一个新的游戏项目，游戏是这样的，场上一共有 n 个气球，它们的编号是0到n-1，然后每个气球上还有一个数字，我们使用数组nums来保存这些数字。

　　现在游戏要求刚刚戳破所有的气球。每当刚刚戳破一个气球i时，刚刚可以获得nums[left] * nums[i] * nums[right]个积分。这里的left和right指的是和i相邻的两个气球的序号。（注意每当刚刚戳破了气球i后，气球left和气球right就变成了相邻的气球。）

　　求所能获得积分的最大值。

输入数据

　　输入中有若干组测试样例，第一行为一个正整数T(T≤1000)，表示测试样例组数。每组测试样例包含2部分： 第一部分有一行，包含1个正整数n（0≤n≤500），第二部分为一行，有n个数，第i个数表示num[i],(0≤num[i]≤100)。

输出数据

对每组测试数据，单独输出一行答案，表示最大的积分值

样例输入

1
2
3
1
4
3 1 5 8

样例输出

1
167
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
#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
public:
	int maxCoins(vector<int>& nums) {
		int n = nums.size();
		vector<vector<int>> rec(n + 2, vector<int>(n + 2));
		vector<int> val(n + 2);
		val[0] = val[n + 1] = 1;
		for (int i = 1; i <= n; i++) {
			val[i] = nums[i - 1];
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = i + 2; j <= n + 1; j++) {
				for (int k = i + 1; k < j; k++) {
					int sum = val[i] * val[k] * val[j];
					sum += rec[i][k] + rec[k][j];
					rec[i][j] = max(rec[i][j], sum);
				}
			}
		}
		return rec[0][n + 1];
	}
}s;
int main()
{
	int T, n, tmp;
	vector<int> num;
	cin >> T;
	for (int j=0;j<T;j++)
	{
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> tmp;
			num.push_back(tmp);
		}
		cout << s.maxCoins(num) << endl;
		num.clear();
	}
	return 0;
}

动态规划

A

Problem A. 晴天小猪历险记之Hill

时间限制 1000 ms
内存限制 128 MB

题目描述

　　这一天，他来到了一座深山的山脚下，因为只有这座深山中的一位隐者才知道这种药草的所在。但是上山的路错综复杂，由于小小猪的病情，晴天小猪想找一条需时最少的路到达山顶，但现在它一头雾水，所以向你求助。
　　山用一个三角形表示，从山顶依次向下有1段、2段、3段等山路，每一段用一个数字T（1< =T< =100）表示，代表晴天小猪在这一段山路上需要爬的时间，每一次它都可以朝左、右、左上、右上四个方向走（注意：在任意一层的第一段也可以走到本层的最后一段或上一层的最后一段）。
　　晴天小猪从山的左下角出发，目的地为山顶，即隐者的小屋。

输入数据

　　第一行有一个数 n (2≤n≤1000)，n (2≤n≤1000)， 表示山的高度。
　　从第二行至第 n+1n+1 行，第 i+1i+1 行有 ii 个数，每个数表示晴天小猪在这一段山路上需要爬的时间。

输出数据

　　一个数，即晴天小猪所需要的最短时间。

样例输入

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

样例输出

1
10

样例说明

在山的两侧的走法略有特殊，请自己模拟一下，开始我自己都弄错了……

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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#define MaxSize 1050
using namespace std;
const int MaxNum = 987654321;
int n, mountain[MaxSize][MaxSize], dp[MaxSize][MaxSize];
int sum(int x, int y)
{
	return x + y;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			scanf("%d", &mountain[i][j]);
		}
	}
	for (int i = 0; i <= n + 1; i++)
	{
		for (int j = 0; j <= 1010; j++)
		{
			dp[i][j] = MaxNum;
		}
	}
	dp[n][1] = 0;
	for (int i = n; i >= 1; i--)
	{
		for (int j = 1; j <= i; j++)
		{
			if (j == 1)
				dp[i][j] = min(min(dp[i][j], dp[i + 1][j] + mountain[i + 1][j]), min(dp[i + 1][i + 1] + mountain[i + 1][i + 1], dp[i + 1][j + 1] + mountain[i + 1][j + 1]));
			else if (j == i)
				dp[i][j] = min(dp[i][j], min(dp[i + 1][1] + mountain[i + 1][1], min(dp[i + 1][j + 1] + mountain[i + 1][j + 1], dp[i + 1][j] + mountain[i + 1][j])));
			else
				dp[i][j] = min(dp[i][j], min(dp[i + 1][j + 1] + mountain[i + 1][j + 1], dp[i + 1][j] + mountain[i + 1][j]));
		}
		dp[i][1] = min(dp[i][1], dp[i][i] + mountain[i][i]);
		for (int j = 2; j <= i; j++)
			dp[i][j] = min(dp[i][j], dp[i][j - 1] + mountain[i][j - 1]);
		dp[i][n] = min(dp[i][n], dp[i][1] + mountain[i][1]);
		for (int j = n - 1; j >= 1; j--)
			dp[i][j] = min(dp[i][j], dp[i][j + 1] + mountain[i][j + 1]);
	}
	cout << sum(dp[1][1],mountain[1][1]);
	return 0;
}

B

Problem B. 清帝之惑之顺治

时间限制 1000 ms
内存限制 128 MB

题目描述

　　顺治喜欢滑雪，这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待太监们来载你。顺治想知道载一个区域中最长的滑坡。
　　区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：

　　 1 2 3 4 5
　　16 17 18 19 6
　　15 24 25 20 7
　　14 23 22 21 8
　　13 12 11 10 9

　　顺治可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。

输入数据

　　输入的第一行表示区域的行数 RR 和列数 C (1≤R,C≤500)C (1≤R,C≤500) 。下面是 RR 行，每行有 CC 个整数，代表高度 h,0≤h<103h,0≤h<103 。

输出数据

　　输出最长区域的长度。

样例输入

1
2
3
4
5
6
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

1
25
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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int high[550][550], dp[550][550];
int xx, yy, max_ans;
bool inmap(int x, int y)
{
	return x >= 0 && x < xx&& y >= 0 && y < yy;
}
int solve(int x, int y)
{
	if (dp[x][y])
		return dp[x][y];
	dp[x][y] = 1;
	int xu = x, yu = y - 1, xd = x, yd = y + 1, xr = x + 1, yr = y, xl = x - 1, yl = y;
	if (inmap(xu, yu) && high[xu][yu] > high[x][y])
	{
		dp[x][y] = max(dp[x][y], solve(xu, yu)+1);
	}
	if (inmap(xd, yd) && high[xd][yd] > high[x][y])
	{
		dp[x][y] = max(dp[x][y], solve(xd, yd)+1);
	}
	if (inmap(xl, yl) && high[xl][yl] > high[x][y])
	{
		dp[x][y] = max(dp[x][y], solve(xl, yl)+1);
	}
	if (inmap(xr, yr) && high[xr][yr] > high[x][y])
	{
		dp[x][y] = max(dp[x][y], solve(xr, yr)+1);
	}
	return dp[x][y];
}
int main()
{

	cin >> xx >> yy;
	for (int i = 0; i < xx; i++)
		for (int j = 0; j < yy; j++) {
			cin >> high[i][j];
		}
	max_ans = 0;
	for (int i = 0; i < xx; i++)
		for (int j = 0; j < yy; j++)
		{
			int tmp = solve(i, j);
			if (tmp > max_ans)
				max_ans = tmp;
		}
	cout << max_ans;
	return 0;
}

C

Problem C. 积木城堡

时间限制 1000 ms
内存限制 128 MB

题目描述

XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。
小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。
任务：
请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

输入数据

第一行是一个整数 N (N≤100)，N (N≤100)， 表示一共有几座城堡。以下 NN 行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。

输出数据

一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出 00 。

样例输入

1
2
3
2
2 1 –1
3 2 1 –1

样例输出

1
3

样例说明

原数据有误,不知我修正后是不是对?

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
#include <stdio.h>
#define MaxSize 105
int a[MaxSize], dp[MaxSize][MaxSize * MaxSize], n;
int solve(int v)
{
    for (int i = 0; i < n; i++)
        if (dp[i][v] == 0)
            return 0;
    return 1;
}

int main()
{
    int ans;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int cnt = 0, sum = 0;
        while (1)
        {
            scanf("%d", &a[cnt]);
            if (a[cnt] == -1)
            {
                break;
            }
            sum = sum + a[cnt];
            cnt++;
        }
        dp[i][0] = 1;
        for (int j = 0; j < cnt; j++)
            for (int k = sum; k >= a[j]; k--)
                if (dp[i][k - a[j]])
                {
                    dp[i][k] = 1;
                }
    }
    ans = 10001;
    while (true)
    {
        if (dp[0][ans] != 0)
            break;
        ans--;
    }
    while (true)
    {
        if (solve(ans) != 0)
            break;
        ans--;
    }
    printf("%d\n", ans);
    return 0;
}

D

Problem D. Warcraft III 守望者的烦恼

时间限制 1000 ms
内存限制 128 MB

题目描述

头脑并不发达的warden最近在思考一个问题，她的闪烁技能是可以升级的，k级的闪烁技能最多可以向前移动k个监狱，一共有n个监狱要视察，她从入口进去，一路上有n个监狱，而且不会往回走，当然她并不用每个监狱都视察，但是她最后一定要到第n个监狱里去，因为监狱的出口在那里，但是她并不一定要到第1个监狱。
守望者warden现在想知道，她在拥有k级闪烁技能时视察n个监狱一共有多少种方案？

输入数据

第一行是闪烁技能的等级 k (1≤k≤10)k (1≤k≤10)
第二行是监狱的个数 n (1≤n≤231−1)n (1≤n≤231−1)

输出数据

由于方案个数会很多，所以输出它 mod 7777777后的结果就行了

样例输入

1
2
2
4

样例输出

1
5

样例说明

把监狱编号1 2 3 4,闪烁技能为2级，
一共有5种方案
→1→2→3→4
→2→3→4
→2→4
→1→3→4
→1→2→4

小提示：建议用int64，否则可能会溢出

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define mod 7777777
using namespace std;
struct matrix
{
    ll s[15][15];
} a, b;
int n, k;

matrix Matrix(matrix x, matrix y)
{
    matrix c;
    memset(c.s, 0, sizeof(c.s));
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            for (int kk = 1; kk <= k; kk++)
            {
                c.s[i][j] += x.s[i][kk] * y.s[kk][j];
                c.s[i][j] %= mod;
            }

    return c;
}
void init_()
{
    cin >> k >> n;
    memset(a.s, 0, sizeof(a.s));
    memset(b.s, 0, sizeof(b.s));
}
int main()
{
    init_();
    a.s[k][k] = 1; //初始化，dp[1]=1
    for (int i = 1; i < k; i++)
        b.s[i][i + 1] = 1;
    for (int i = 1; i <= k; i++)
        b.s[k][i] = 1;
    while (n)
    { //dp[n]需要乘以n个矩阵b
        if (n & 1)
            a = Matrix(a, b);
        b = Matrix(b, b);
        n >>= 1;
    }
    printf("%lld", a.s[k][k]);
    return 0;
}

E

Problem E. 加分二叉树

时间限制 1000 ms
内存限制 128 MB

题目描述

　　设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：
　　subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数
　　若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。
　　试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；
　　（1）tree的最高加分
　　（2）tree的前序遍历

输入数据

　　第 11 行：一个整数 n (n＜30)，n (n＜30)， 为节点个数。
　　第 22 行 ：n：n 个用空格隔开的整数，为每个节点的分数（分数 ＜100）＜100） 。

输出数据

　　第 11 行：一个整数，为最高加分（结果不会超过 4,000,000,000）4,000,000,000） 。
　　第 22 行 ：n：n 个用空格隔开的整数，为该树的前序遍历。
若存在多种前序遍历均为最高加分，则输出字典序最小的前序遍历

样例输入

1
2
5
5 7 1 2 10

样例输出

1
2
145
3 1 2 4 5
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
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
int n, a[40], root[40][40];
ll dp[40][40];
ll dfs(int L, int R)
{
    if (L > R)
        return 1; //因为要左右子节点相乘，所以如果是空则给1
    if (dp[L][R])
        return dp[L][R]; //关键一步，记忆化，以前走过那就直接返回结果
    ll maxn = 0;
    for (int i = L; i < R; i++)
    {
        ll t = dfs(L, i - 1) * dfs(i + 1, R) + a[i];
        if (t > maxn)
        {
            maxn = t;
            root[L][R] = i;
        }
    }
    return dp[L][R] = maxn;
}

void dg(int L, int R)
{
    if (L > R)
        return; //防止出现 L >R
    printf("%d ", root[L][R]);
    dg(L, root[L][R] - 1);
    dg(root[L][R] + 1, R);
}
void init_()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i][i] = a[i];
        root[i][i] = i;
    }
}
int main()
{
    init_();
    printf("%lld\n", dfs(1, n));
    dg(1, n);
    return 0;
}

期中

A

Problem A. 陶陶摘苹果

时间限制 1000 ms
内存限制 128 MB

题目描述

　　陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。
　　现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

输入数据

　　输入包括两行数据。第一行包含 1010 个100到200之间（包括100和200）的整数（以厘米为单位）分别表示 1010 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

输出数据

输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

样例输入

1
2
100 200 150 140 129 134 167 198 200 111
110

样例输出

1
5

B

Problem B. 选数

时间限制 1000 ms
内存限制 128 MB

题目描述

　　已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
　　3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
　　现在，要求你计算出和为素数共有多少种。
　　例如上例，只有一种的和为素数：3＋7＋19＝29）。

输入数据

n , k （1< =n< =20，k＜n）
x1,x2，…,xn （1< =xi< =5e5）

输出数据

一个整数（满足条件的种数）。

样例输入

1
2
4 3
3 7 12 19

样例输出

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
#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x){
	if(x < 2)
		return 0;
	for(int i = 2; i <= sqrt(x); i++)
		if(!(x % i))
			return 0;
	return 1;
}

int n, k, ans;
int a[30];
void force(int sum, int now, int used){
	if(used == k){
		if(isPrime(sum))
			ans++;
		return ;
	}
	if(n - now + used < k)
		return ;
	force(sum + a[now], now + 1, used + 1);
	force(sum, now + 1, used);
}

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	force(0, 0, 0);
	cout << ans << endl;
	return 0;
}

C

Problem C. Ricky队形

时间限制 1000 ms
内存限制 256 MB

题目描述

Ricky班里有n(2<=n<=100000)个人，每个人有一个学号ai(1<=ai<=n)，保证学号ai互不相同。Ricky手里有一张班级合影，他发现虽然大家是按身高从低到高排好队的，但如果按学号看的话却不一定是从小到大，他想看一看如果按照学号来看，这个队排的有多乱。Ricky把混乱度定义为队列中逆序对的个数，即：如果从前往后看，大家正好是按照学号从小到大排列的，那逆序对为0个，混乱度为0；而每能找到两个人形成了学号大同学的在前，学号小的在后（即i < j且ai > aj），就称其为一个逆序对，混乱度计数也要加1。由于Ricky班里人可能很多，Ricky实在数不过来了，现在告诉你合影上同学们的学号（按从前往后），请你帮忙编写程序计算一下混乱度，满足一下Ricky的好奇心。

输入数据

第一行有一个整数n(2<=n<=100000)，表示Ricky班上的人数； 第二行有n个整数a1,a2,…,an(1<=ai<=n)，表示合影上同学们的学号。

输出数据

输出一个整数，表示合影上排列的混乱度（逆序对个数）

样例输入

1
2
5
1 3 4 2 5

样例输出

1
2

样例说明

其中(3,2) (4,2)形成两个逆序对，所以混乱度为2

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
#include <bits/stdc++.h>
using namespace std;

int tmp[112345], a[112345], n;
long long ans;
void mysort(int l, int r){
	if(l >= r)
		return ;
	int mid = (l + r) >> 1;
	mysort(l, mid);
	mysort(mid + 1, r);
	int i = l, j = mid + 1, k = 0;
	while(i <= mid && j <= r){
		if(a[i] <= a[j])
			tmp[k++] = a[i++];
		else{
			ans += mid - i + 1;
			tmp[k++] = a[j++]; 
		}
	}
	for(; i <= mid; i++)
		tmp[k++] = a[i];
	for(; j <= r; j++)
		tmp[k++] = a[j];
	for(i = 0; i < k; i++)
		a[i + l] = tmp[i];
}

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	mysort(0, n - 1);
	printf("%lld\n", ans);
	return 0;
}

D

Problem D. Ricky的蔬菜沙拉

时间限制 1000 ms
内存限制 256 MB

题目描述

Ricky决定从今天起开始减肥，所以晚上就吃蔬菜沙拉了。现在Ricky家里就有n种食材（每种只有一份），他准备从中挑选一些来制作沙拉。每样食材都有两种属性，美味程度Di，以及热量值Ci。吃饭很讲究的Ricky有个小小的要求，最后挑选的所有食材的美味程度之和必须是热量值之和的k倍。现在想请你来帮忙计算，在满足Ricky的要求的情况下，挑选的所有食材美味值之和最大是多少。如果无法制作出符合要求的沙拉，请输出-1。

输入数据

第一行有两个整数n，k（1 ≤ n ≤ 100, 1 ≤ k ≤ 10），表示食材的数量，以及Ricky要求的倍数；
第二行有n个整数D1,D2,…,Dn (1 ≤ Di ≤ 100)，表示每个食材的美味程度；
第三行有n个整数C1,C2,…,Cn (1 ≤ Ci ≤ 100)，表示每个食材的热量值。

输出数据

如果无法制作出符合要求的沙拉，输出-1；否则输出一个整数，表示挑选的所有食材美味值之和最大值。

样例输入

1
2
3
3 2
10 8 1
2 7 1

样例输出

1
18

样例说明

再给一组样例：
样例输入：
5 3
4 4 4 4 4
2 2 2 2 2
样例输出：
-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
#include <bits/stdc++.h>
using namespace std;

int n, k, add;
int d[110], c[110], dt[110];
int f1[11234], f2[11234];
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> d[i];
	for(int i = 0; i < n; i++){
		cin >> c[i];
		dt[i] = d[i] - k * c[i];
		if(dt[i] == 0)
			add += d[i];
	}
	for(int i = 0; i < 11234; i++)
		f1[i] = f2[i] = -1;
	for(int i = 0; i < n; i++)
		if(dt[i] > 0)
			for(int j = 10000; j >= dt[i]; j--){
				if(f1[j - dt[i]] != -1)
					f1[j] = max(f1[j], f1[j - dt[i]] + d[i]);
				if(j == dt[i])
					f1[j] = max(f1[j], d[i]); 
			}
	for(int i = 0; i < n; i++)
		if(dt[i] < 0)
			for(int j = 10000; j >= -dt[i]; j--){
				if(f2[j + dt[i]] != -1)
					f2[j] = max(f2[j], f2[j + dt[i]] + d[i]);
				if(j == -dt[i])
					f2[j] = max(f2[j], d[i]); 
			}
	int ans = -1;
	for(int i = 0; i < 10000; i++)
		if(f1[i] != -1 && f2[i] != -1)
			ans = max(ans, f1[i] + f2[i]);
	if(add != 0){
		if(ans == -1)
			ans = add;
		else
			ans += add;
	}
	cout << ans << endl;
	return 0;
}

E

Problem E. 24点游戏

时间限制 1000 ms
内存限制 128 MB

题目描述

　　几十年前全世界就流行一种数字扑克游戏，至今仍有人乐此不疲．在中国我们把这种游戏称为“算24点”。您作为游戏者将得到4个1-13（在扑克牌里用A代替1，J代替11，Q代替12，K代替13）之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算（可以使用+、-、*、/、括号），判断运算结果是否等于24。能输出1，不能输出0。

输入数据

四个牌面值。牌面值与牌面值之间用一个空格隔开。

输出数据

输出 00 或 11 。

样例输入

1
3 8 10 Q

样例输出

1
1

样例说明

Q×(10/(8-3))=24

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
#include <bits/stdc++.h>
using namespace std;

int ctoi[100];
bool ans;
struct item{
	float num[4];
	bool sign[4];
};
void force(int n, item a){
	if(n == 1){
		if(a.num[0] == 24)
			ans = 1;
		return ;
	}
	item b;
	memset(b.sign, 0, sizeof(b.sign));
	for(int i = 0; i < n; i++){
		a.sign[i] = 1;
		for(int j = 0; j < n; j++)
			if(i != j){
				a.sign[j] = 1;
				int l = 0;
				for(int k = 0; k < n; k++)
					if(!a.sign[k])
						b.num[l++] = a.num[k];
				b.num[l] = a.num[i] + a.num[j];
				force(n - 1, b);
				b.num[l] = a.num[i] - a.num[j];
				force(n - 1, b);
				b.num[l] = a.num[i] * a.num[j];
				force(n - 1, b);
				if(a.num[j] != 0){
					b.num[l] = a.num[i] / a.num[j];
					force(n - 1, b); 
				}
				a.sign[j] = 0;
			}
		a.sign[i] = 0;
	}
}

int main()
{
	for(int i = 0; i < 10; i++)
		ctoi[i + 48] = i;
	ctoi['A'] = 1;
	ctoi['J'] = 11;
	ctoi['Q'] = 12;
	ctoi['K'] = 13;
	
	item a;
	memset(a.sign, 0, sizeof(a.sign));
	for(int i = 0; i < 4; i++){
		char x[5];
		cin >> x;
		if(strlen(x) == 2)
			a.num[i] = 10;
		else
			a.num[i] = ctoi[x[0]];
	}
	force(4, a);
	cout << ans << endl;
	return 0;
}

贪心与图

A

Problem A. 最小差距

时间限制 1000 ms
内存限制 128 MB

题目描述

　　给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。
　　例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。
　　给定N个不同的0~9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？

输入数据

　　第一行包括一个数 T (T≤1000)，T (T≤1000)， 为测试数据的组数。
　　每组数据包括两行，第一行为一个数 N (2≤N≤10)，N (2≤N≤10)， 表示数字的个数。下面一行为 NN 个不同的一位数字。

输出数据

TT 行，每行一个数，表示第 ii 个数据的答案。即最小的差的绝对值。

样例输入

1
2
3
4
5
2
6
0 1 2 4 6 7
4
1 6 3 4

样例输出

1
2
28
5
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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
int a[15]; 
int visited[15];
 
int odd(int n){
	if(a[1]==0){
		int temp=a[1];
		a[1]=a[2];
		a[2]=temp;
	}
	int s1 = 0, s2 = 0;
	for(int i=1; i<=n/2+1; i++)
		s1 = s1*10 + a[i];
	for(int i=n; i>n/2+1; i--)
		s2 = s2*10 + a[i];
	return s1-s2;
}
 
int even(int n){
	int res = INF;
	for(int i=2; i<=n; i++){
		if(a[i-1]){
			memset(visited, 0, sizeof(visited));
			int s1=a[i], s2=a[i-1];
			visited[i]=1;
			visited[i-1]=1;
			int left=1, right=n;
			for(int j=1; j<=(n-2)/2; j++){//每一轮选出两个数字 
				while(visited[left]) left++;
				while(visited[right]) right--;
				visited[left]=1;
				visited[right]=1;
				s1 = s1*10 + a[left];
				s2 = s2*10 + a[right];
			}
			res = min(res, s1-s2);
		}
	}
	return res;
}
 
int main(){
	int T;
	cin>>T;
	
	for (int id = 0; id < T; id++)
	{
		int N, ans;
		cin >> N;
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= N; i++)
			cin >> a[i];

		sort(a + 1, a + N + 1);
		if (N == 2) {
			ans = a[2] - a[1];
		}
		else if (N % 2 == 1) {
			ans = odd(N);
		}
		else {
			ans = even(N);
		}
		cout << ans << endl;
	}
	return 0;
}

B

Problem B. 合并果子

时间限制 1000 ms
内存限制 128 MB

题目描述

　　在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
　　每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
　　因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
　　例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入数据

输入包括两行，第一行是一个整数 n (1<＝n<103)，n (1<＝n<103)， 表示果子的种类数。第二行包含 nn 个整数，用空格分隔，第 ii 个整数 ai (1<＝ai<2×103)ai (1<＝ai<2×103) 是第 ii 种果子的数目。

输出数据

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 231231 。

样例输入

1
2
3 
1 2 9

样例输出

1
15 
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
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
	int n, ans = 0,x;
	cin >> n;
	//这里使用优先队列的方法
	priority_queue < int, vector <int>, greater <int> > q;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		q.push(x);
	}
	for (int i=0;i<n-1;i++)
	{
		int x1 = q.top();
		q.pop();
		int x2 = q.top();
		q.pop();
		ans += x1 + x2;
		q.push(x1 + x2);
	}
	cout << ans << endl;
}

C

Problem C. 北京2008的挂钟

时间限制 1000 ms
内存限制 128 MB

题目描述

　　在2008北京奥运会雄伟的主会场的墙上，挂着如上图所示的3*3的九个挂钟（一开始指针即时针指向的位置请根据输入数据调整）。然而此次奥运会给与了大家一个机会，去用最少的移动操作改变上面的挂钟的时间全部为12点正（我们只考虑时针）。然而每一次操作并不是任意的，我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行，每一个挂钟顺时针转动90度。列表如下：

　　操作 指定的操作挂钟
　　 1　　　　 ABDE
　　 2　　　　 ABC
　　 3　　　　 BCEF
　　 4　　　　 ADG
　　 5　　　　 BDEFH
　　 6　　　　 CFI
　　 7　　　　 DEGH
　　 8　　　　 GHI
　　 9　　　　 EFHI

输入数据

　　你的程序按照标准的 3∗33∗3 格式读入，一共 99 个 0−30−3 的数。 00 代表 1212 点 ，1，1 代表 33 点 ，2，2 代表 66 点 ，3，3 代表 99 点。
　　Your program is to read from standard input. Nine numbers give the start positions of the dials. 0=12 o’clock, 1=3 o’clock, 2=6 o’clock, 3=9 o’clock.

输出数据

　　你的程序需要写出标准的输出。输出一个最短的能够使所有挂钟指向 1212 点的移动操作序列，中间以空格隔开，最后有空格，加回车。这一条最短操作需要是所有最短操作中最小的，也就是说选择最小的第一个操作数，如果第一个操作数相等，那么选择最小的第二个操作数……以此类推。值得肯定的是，这一条操作序列是唯一的。
　　Your program is to write to standard output. Output a shortest sorted sequence of moves (numbers), which returns all the dials to 12 o’clock. You are convinced that the answer is unique.

样例输入

1
2
3
3 3 0
2 2 2
2 1 2

样例输出

1
4 5 8 9
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
#include<iostream>
using namespace std;

const int way[9][9] = { { 1,1,0,1,1,0,0,0,0 },	// 操作1	ABDE
						{ 1,1,1,0,0,0,0,0,0 },	// 操作2	ABC
						{ 0,1,1,0,1,1,0,0,0 },	// 操作3	BCEF
						{ 1,0,0,1,0,0,1,0,0 },	// 操作4	ADG
						{ 0,1,0,1,1,1,0,1,0 },	// 操作5	BDEFH
						{ 0,0,1,0,0,1,0,0,1 },	// 操作6	CFI
						{ 0,0,0,1,1,0,1,1,0 },	// 操作7	DEGH
						{ 0,0,0,0,0,0,1,1,1 },	// 操作8	GHI
						{ 0,0,0,0,1,1,0,1,1 } 	// 操作9	EFHI
};
bool judge;//判断是否调整完成
int x[9], ans[9];

void dfs(int num)
{
	if (num == 9)//9种方式全部搜完
	{
		for (int i = 0; i < 9; i++)
		{
			if (x[i] % 4 != 0)//有不是12点的钟
				return;
		}
		judge = true;//全部调整完成
		return;
	}

	for (int i = 0; i <= 3; i++)
	{
		ans[num] = i;//第（i+1）钟方式的数量
		for (int j = 0; j < 9; j++)
		{
			x[j] += way[num][j] * i;//改变
		}
		dfs(num + 1);//深搜
		if (judge)//此时已经调整完成，而调整方式有且只有一种，因此可以输出答案
			return;
		for (int j = 0; j < 9; j++)
		{
			x[j] -= way[num][j] * i;//回溯
		}
	}
}
void printRes()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < ans[i]; j++)
		{
			cout << i + 1 << ' ';
		}
	}
	cout << endl;
}
int main()
{
	for (int i = 0; i < 9; i++)
	{
		cin >> x[i];
	}

	dfs(0);
	printRes();
	return 0;
}

D

Problem D. 毒药？解药？

时间限制 1000 ms
内存限制 128 MB

题目描述

　　羽毛笔和im是抽签到同一个考场的，她们突然闻到一阵刺鼻的化学试剂的气味。
　　机灵鼠：（头都不抬）你们是考生么？还在门口磨蹭什么？快进来帮我忙！！……怎么还不进来？你们拖赛，拖赛，把你们的青春都拖掉赛……
　　im：开…开策了> <
　　羽毛笔：哎呀~~机灵鼠大人要我们帮什么忙？^^
　　机灵鼠：你们看这里的这些药，都是我研制的对付各种症状的解药。可是我一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症……（im：那…那是解药还是毒药啊？！）……经过我天才的努力（背景：我是天才！！），终于弄清了每种药的具体性能（路人甲：那是你自己配的吗？--），我会把每种药能治的病症和能使人患上的病症列一张清单给你们，然后你们要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声，病症的数目不超过10种（小呆：偶是好人吧^^），我的药是用不完的，就是说每种药剂都可以被重复使用。给你们的单子里第一行是病症的总数n，第二行是药剂的种类m（0< m< =100），以下有m行，每行有n个数字用空格隔开，文件的第i+2行的n个数字中，如果第j个数为1，就表示第i种药可以治愈病症j（如果患有这种病的话则治愈，没有这种病则无影响），如果为0表示无影响，如果为-1表示反而能使人得上这种病（无病患上，有病无影响）。我制的药任何两种性能都不同。你们只要给我用的最少的药剂数就可以了。给你们个样例：

输入数据

输出数据

样例输入

1
2
3
4
3
2
1 0 1
-1 1 0

样例输出

1
2

样例说明

　　其实还有可能用尽了所有的药也不能将所有病治愈（真是不好意思嗬^^bb），那样的话你们只要写上“The patient will be dead.”就可以了。
　　im：做不出来啊哇啊啊啊（暴走中）
　　羽毛笔：哎呀~~im……来来吃药了。^^

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
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define maxn 15
#define  maxm 110
#define maxg 1040

bool stateT[maxn], hashT[maxg];
int mp[maxm][maxn];
int stateI[maxg][maxn];
int n, m, finish;

int Hash(bool a[]) {
	int x = 1, s = 0;
	for (int i = 1; i <= n; i++) {
		s += x * a[i];
		x *= 2;
	}
	return s;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++)
			cin >> mp[i][j];
	int l = 0, r = 1;
	finish = (1 << n) - 1;
	while (l < r) {
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (mp[i][j] == 1) stateT[j] = 1;
				else if (mp[i][j] == -1) stateT[j] = 0;
				else stateT[j] = stateI[l][j];
			}
			int x = Hash(stateT);
			if (x == finish) {
				cout << stateI[l][0] + 1 << endl;
				return 0;
			}
			if (!hashT[x]) {
				hashT[x] = 1;
				stateI[r][0] = stateI[l][0] + 1;
				for (int j = 1; j <= n; j++) stateI[r][j] = stateT[j];
				r++;
			}
		}
		l++;
	}
	cout << "The patient will be dead." << endl;
	return 0;
}

E

Problem E. 矩形覆盖

时间限制 1000 ms
内存限制 128 MB

题目描述

　　在平面上有 n 个点（n < = 50），每个点用一对整数坐标表示。例如：当 n＝4 时，4个点的坐标分另为：p1（1，1），p2（2，2），p3（3，6），P4（0，7）。
　　这些点可以用 k 个矩形（1< =k< =4）全部覆盖，矩形的边平行于坐标轴。当 k=2 时，可用如图二的两个矩形 sl，s2 覆盖，s1，s2 面积和为 4。问题是当 n 个点坐标和 k 给出后，怎样才能使得覆盖所有点的 k 个矩形的面积之和为最小呢。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。

输入数据

格式为
n k
xl y1
x2 y2
… …
xn yn （0< =xi,yi< =500)

输出数据

一个整数，即满足条件的最小的矩形面积之和。

样例输入

1
2
3
4
5
4 2
1 1
2 2
3 6
0 7

样例输出

1
4
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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m;//输入值
int SquareAns = 10000000;//结果
struct node {
	int x, y;
}Node[510];

struct node2 {
	int l, r, u, d;
	bool IsChoosed;
}rectangle[5];

bool IsNodeInRectangle(node2 a, int x, int y)
{
	if (x <= a.r && x >= a.l && y <= a.u && y >= a.d)
		return 1;
	return 0;
}

bool IsRectangleInRectangle(node2 a, node2 b)  //判断是否包含 
{
	if (IsNodeInRectangle(a, b.l, b.u)) return 1;  //左上角   任何一个顶点在已知矩阵内就不合法 
	if (IsNodeInRectangle(a, b.l, b.d)) return 1;  //左下角 
	if (IsNodeInRectangle(a, b.r, b.u)) return 1;  //右上角 
	if (IsNodeInRectangle(a, b.r, b.d)) return 1;  //右下角 
	return 0;
}

int Search(int t)
{
	int i, j, square = 0;
	for (i = 1; i <= m; i++)  
	{
		if (rectangle[i].IsChoosed)  
		{
			for (j = 1; j <= m; j++)
			{
				if (i != j && rectangle[j].IsChoosed && IsRectangleInRectangle(rectangle[i], rectangle[j]))  
					return 0;  
			}
		}
		square += (rectangle[i].r - rectangle[i].l) * (rectangle[i].u - rectangle[i].d);  
	}
	if (square >= SquareAns)  
		return 0;
	if (t > n)   
	{
		SquareAns = square;//满足条件更新SquareAns
		return 0;
	}
	for (i = 1; i <= m; i++)  
	{
		node2 tmp = rectangle[i];
		if (rectangle[i].IsChoosed == 0)  
		{
			rectangle[i].IsChoosed = 1;
			rectangle[i].l = rectangle[i].r = Node[t].x;
			rectangle[i].u = rectangle[i].d = Node[t].y;
			Search(t + 1);
			rectangle[i] = tmp;   
		}
		else
		{
			rectangle[i].l = min(rectangle[i].l, Node[t].x);  
			rectangle[i].r = max(rectangle[i].r, Node[t].x);
			rectangle[i].u = max(rectangle[i].u, Node[t].y);
			rectangle[i].d = min(rectangle[i].d, Node[t].y);
			Search(t + 1);
			rectangle[i] = tmp;
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m); //输入
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &Node[i].x, &Node[i].y);
	Search(1);
	printf("%d", SquareAns);
	return 0;
}

F

Problem F. 传染病防治

时间限制 1000 ms
内存限制 128 MB

题目描述

　　研究表明，这种传染病的传播具有两种很特殊的性质；
　　第一是它的传播途径是树型的，一个人X只可能被某个特定的人Y感染，只要Y不
得病，或者是XY之间的传播途径被切断，则X就不会得病。
　　第二是，这种疾病的传播有周期性，在一个疾病传播周期之内，传染病将只会感染一
代患者，而不会再传播给下一代。
　　这些性质大大减轻了蓬莱国疾病防控的压力，并且他们已经得到了国内部分易感人群
的潜在传播途径图（一棵树）。但是，麻烦还没有结束。由于蓬莱国疾控中心人手不够，同时也缺乏强大的技术，以致他们在一个疾病传播周期内，只能设法切断一条传播途径，而没有被控制的传播途径就会引起更多的易感人群被感染（也就是与当前已经被感染的人有传播途径相连，且连接途径没有被切断的人群）。当不可能有健康人被感染时，疾病就中止传播。所以，蓬莱国疾控中心要制定出一个切断传播途径的顺序，以使尽量少的人被感染。你的程序要针对给定的树，找出合适的切断顺序。 　　

输入数据

　　输入格式的第一行是两个整数 n (1≤n≤300)n (1≤n≤300) 和 pp 。接下来 pp 行，每一行有两个整数 ii
和 j，j， 表示节点 ii 和 jj 间有边相连（意即，第 ii 人和第 jj 人之间有传播途径相连）。其中节点
11 是已经被感染的患者。

输出数据

只有一行，输出总共被感染的人数。

样例输入

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

样例输出

1
3
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
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define maxn 305
int n, m;//总结点数和节点联系
int map[maxn][maxn] = { 0 };
int ans = 0x7ffffff;
int child[maxn];
void dfs(int tree[maxn], int s, int d, int res)
{
	int son[maxn];
	int cur = 0;
	for (int i = 1; i <= s; i++)
	{
		int& a = tree[i];
		if (a == d)    continue;
		for (int i = 1; i <= n; i++)
			if (map[a][i])
				son[++cur] = i;
	}
	if (!cur)
		ans = min(ans, res);
	else
	{
		for (int i = 1; i <= cur; i++)
			if (res + cur - 1 <= ans)
				dfs(son, cur, son[i], res + cur - 1);
	}
}
int main()
{
	cin >> n >> m;
	int a, b;
	int cur = 0;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		if (a > b)
			swap(a, b);
		map[a][b] = 1;
		if (a == 1)    child[++cur] = b;//记录1(根)的子节点
	}
	for (int i = 1; i <= cur; i++)
		dfs(child, cur, child[i], cur);
	cout << ans << endl;
	return 0;
}