题意 给你n种面额不同的金币和每种金币的个数 求这些金币能组合成的面额在m内有多少种

还是明显的背包问题 d[i]表示这些金币在i内能组合成的最大面额 初始化d为负无穷 d[0]=0 这样就可以保证d[i]恰好为i时才能为正值

原因可以自己想想 然后就用背包背吧 直接多重背包也可以过 但是分成多重背包和完全背包要快一点

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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105, M = 100005;
int main()
{
    int n, m, val[N], num[N], d[M], ans;
    while (scanf ("%d%d", &n, &m), n && m)
    {
        memset (d, 0x8f, sizeof (d));
        d[0] = ans = 0;
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &val[i]);
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &num[i]);
        for (int i = 1; i <= n; ++i)
        {
            if (num[i]*val[i] >= m)
                for (int j = val[i]; j <= m; ++j)
                    d[j] = max (d[j], d[j - val[i]] + val[i]);
            else
            {
                for (int k = 1; k <= num[i]; k *= 2)
                {
                    for (int j = m; j >= k * val[i]; --j)
                        d[j] = max (d[j], d[j - k * val[i]] + k * val[i]);
                    num[i] -= k;
                }
                if (num[i] > 0)
                    for (int j = m; j >= num[i]*val[i]; --j)
                        d[j] = max (d[j], d[j - num[i] * val[i]] + num[i] * val[i]);
            }
        }
        for (int i = 1; i <= m; ++i)
            if (d[i] > 0) ++ans;
        printf ("%d\n", ans);
    }
    return 0;
}

Coins

Problem Description

Whuacmers use coins.They have coins of value A1,A2,A3…An Silverland dollar. One day Hibix opened purse and found there were some coins. He decided to buy a very nice watch in a nearby shop. He wanted to pay the exact price(without change) and he known the price would not more than m.But he didn’t know the exact price of the watch.
You are to write a program which reads n,m,A1,A2,A3…An and C1,C2,C3…Cn corresponding to the number of Tony’s coins of value A1,A2,A3…An then calculate how many prices(form 1 to m) Tony can pay use these coins.
Input

The input contains several test cases. The first line of each test case contains two integers n(1 ≤ n ≤ 100),m(m ≤ 100000).The second line contains 2n integers, denoting A1,A2,A3…An,C1,C2,C3…Cn (1 ≤ Ai ≤ 100000,1 ≤ Ci ≤ 1000). The last test case is followed by two zeros.
Output

For each test case output the answer on a single line.
Sample Input

3 10 1 2 4 2 1 1 2 5 1 4 2 1 0 0
Sample Output

8 4

题意 中文

先把物品重量从小到大排序 d[i][j]表示前i件物品选j对的最小疲劳
若选了第i个物品 那么和它一对的必是第i-1个物品 注意是前i件
i=j/*2时 没有选择 d[i][j]=d[i-2][j-1]+(w[i]-w[i-1])^2
i>j/*2时 存在第i个选或者不选之分
若选了第i个的话 那么问题就转化为在i-2个物品中选j-1个了
若不选第i个的话 问题转化为在i-1个物品中选j个了

那么就有转移方程d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-1])^2)

d是初始化为无穷大的 所以i=j/*2时 d[i-1][j]是等于无穷大的 所以状态转移方程可以统一为

d[i][j]=min(d[i-1][j],d[i-2][j-1]+(w[i]-w[i-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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2014;
int w[N], d[N][N / 2], n, k;

int main()
{
    while (~scanf ("%d%d", &n, &k))
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &w[i]);
        sort (w + 1, w + n + 1);
        memset (d, 0x7f, sizeof (d));
        for (int i = 0; i <= n; ++i)  d[i][0] = 0;
        
        for (int i = 2; i <= n; ++i)
            for (int j = 1; j * 2 <= i; ++j)
                d[i][j] = min (d[i - 1][j], d[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
                
        printf ("%d\n", d[n][k]);
    }
    return 0;
}

搬寝室

Problem Description

搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2/*k件过去就行了.但还是会很累,因为2/*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2/*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
Input

每组输入数据有两行,第一行有两个数n,k(2<=2/*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
Output

对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Sample Input

2 1 1 3
Sample Output

4

题意 求最大相同字符子矩阵 其中一些字符可以转换

其实就是HDU1505 1506的加强版 但是分了a,b,c三种情况 看哪次得到的面积最大

对于某一个情况 可以把该字符和可以转换为该字符的位置赋值0 其它位置赋值１　这样就转化成了求最大全0矩阵的问题了

对于转换后矩阵中的每个点　看他向上有多少个连续0　把这个值存在ｈ数组中　再用l数组和ｒ数组记录ｈ连续大于等于该位置的最左边位置和最右位置　这样包含(i,j)点的最大矩阵面积就是(r[i][j]-l[i][j]+1)/*h[i][j]　面积最大的点就是最大全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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
char s[N][N];
int mat[N][N], l[N][N], r[N][N], h[N][N], n, m, ans;

void makeMat (char a, char b, char c)
{
    memset (mat, 0, sizeof (mat));
    memset (l, 0, sizeof (l));
    memset (r, 0, sizeof (r));
    memset (h, 0, sizeof (h));
    for (int i = 1; i <= n; ++i)
    {
        h[i][0] = h[i][m + 1] = -1;
        for (int j = 1; j <= m; ++j)
        {
            l[i][j] = r[i][j] = j;
            if (s[i][j] == a || s[i][j] == b || s[i][j] == c)  mat[i][j] = 1;
            if (mat[i][j] == 0) h[i][j] = h[i - 1][j] + 1;
        }
    }
}

int solve (char a, char b, char c)
{
    makeMat (a, b, c);
    int aans = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= 1; --j)
            while (h[i][r[i][j] + 1] >= h[i][j])
                r[i][j] = r[i][r[i][j] + 1];

        for (int j = 1; j <= m; ++j)
        {
            while (h[i][l[i][j] - 1] >= h[i][j])
                l[i][j] = l[i][l[i][j] - 1];
            aans = max (aans, (r[i][j] - l[i][j] + 1) * h[i][j]);
        }
    }
    return aans;
}

int main()
{
    while (~scanf ("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%s", s[i] + 1);
        ans = max (solve ('x', 'b', 'c'), solve ('a', 'y', 'c'));
        ans = max (ans, solve ('a', 'b', 'w'));
        printf ("%d\n", ans);
    }
    return 0;
}

Largest Submatrix

Problem Description

Now here is a matrix with letter ‘a’,’b’,’c’,’w’,’x’,’y’,’z’ and you can change ‘w’ to ‘a’ or ‘b’, change ‘x’ to ‘b’ or ‘c’, change ‘y’ to ‘a’ or ‘c’, and change ‘z’ to ‘a’, ‘b’ or ‘c’. After you changed it, what’s the largest submatrix with the same letters you can make?
Input

The input contains multiple test cases. Each test case begins with m and n (1 ≤ m, n ≤ 1000) on line. Then come the elements of a matrix in row-major order on m lines each with n letters. The input ends once EOF is met.
Output

For each test case, output one line containing the number of elements of the largest submatrix of all same letters.
Sample Input

2 4 abcw wxyz
Sample Output

3

题意 给你一个n/*m矩阵 每列都可以随便交换位置 求最优交换后最大的全1子矩阵

又是HDU 1505 1506的变种 但这个更容易了 因为每列都可以交换位置了 那么这一行中所有比i高的都可以与i相邻了 只需要统计这一行有多少个比i高就行了 可以在算出每一行后 把高度大的放前面去 用num[i]记录排序后的列原来的数 这样就有j列比h[i][num[j]]高了 最后的答案也就是max(j/*h[i][num[j]])

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
char mat[N][N];
int num[N], h[N][N], n, m, i;

bool cmp (int a, int b)
{
    return h[i][a] > h[i][b];
}//cmp不能有=

int main()
{
    while (~scanf ("%d%d", &n, &m))
    {
        int ans = 0;
        memset (h, 0, sizeof (h));
        for (i = 1; i <= n; ++i)
            scanf ("%s", mat[i] + 1);
        for (i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                if (mat[i][j] == '1')  h[i][j] = h[i - 1][j] + 1;
                num[j] = j;
            }
            sort (num + 1, num + m + 1, cmp);
            for (int j = 1; j <= m; ++j)
                ans = max (ans, j * h[i][num[j]]);
        }
        printf ("%d\n", ans);
    }
    return 0;
}

Matrix Swapping II

Problem Description

Given an N /* M matrix with each entry equal to 0 or 1. We can find some rectangles in the matrix whose entries are all 1, and we define the maximum area of such rectangle as this matrix’s goodness.
We can swap any two columns any times, and we are to make the goodness of the matrix as large as possible.
Input

There are several test cases in the input. The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 1000). Then N lines follow, each contains M numbers (0 or 1), indicating the N /* M matrix
Output

Output one line for each test case, indicating the maximum possible goodness.
Sample Input

3 4 1011 1001 0001 3 4 1010 1001 0001
Sample Output

4 2 Note: Huge Input, scanf() is recommended.

题意 给你n种长方体 每种都有无穷个 三条棱长为a,b,c 当一个长方体的长宽都小于另一个时 这个长方体就可以堆在另一个上面 求这些长方体能堆起的最大高度

每个长方体都有6种放置方式 但只有三种高度 分别为a,b,c 为了便于操坐 可以把一个长方体分为三个 每个的高度都是唯一的 然后就可以用最长连通来求了 令d[i]表示以第i个长方体为最顶上一个时的最大高度 当第i个长方体的长和宽小于第j个的长和宽或宽和长时 第i个就可以放在第j个上面 即 d[i]=max(d[i],d[j]+a[i].h)

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 35 * 3;
int d[N], n;
struct Cube
{
    int a, b, c;
    Cube (int aa = 0, int bb = 0, int cc = 0) : a (aa), b (bb), c (cc) {}
} cub[N];

int dp (int i)
{
    if (d[i] > 0) return d[i];
    d[i] = cub[i].c;
    for (int j = 1; j <= 3 * n; ++j)
        if ( (cub[i].a < cub[j].a && cub[i].b < cub[j].b) || (cub[i].a < cub[j].b && cub[i].b < cub[j].a))
            d[i] = max (d[i], dp (j) + cub[i].c);
    return d[i];
}

int main()
{
    int cas = 0, ans, a, b, c;
    while (scanf ("%d", &n), n)
    {
        memset (d, 0, sizeof (d));
        for (int i = ans = 0; i < n; ++i)
        {
            scanf ("%d%d%d", &a, &b, &c);
            cub[3 * i + 1] = Cube (a, b, c);
            cub[3 * i + 2] = Cube (a, c, b);
            cub[3 * i + 3] = Cube (b, c, a);
        }
        for (int i = 1; i <= 3 * n; ++i)
            ans = max (ans, dp (i));
        printf ("Case %d: maximum height = %d\n", ++cas, ans);
    }
    return 0;
}

Monkey and Banana

Problem Description

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.
Input

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.
Output

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

Big Event in HDU

Problem Description

Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).
Input

Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 – the total number of different facilities). The next N lines contain an integer V (0<V<=50 –value of facility) and an integer M (0<M<=100 –corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.
Output

For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input

2 10 1 20 1 3 10 1 20 2 30 1 -1
Sample Output

20 10 40 40

题意 把一堆东西尽量分为两份 第一份不小于第二份

把所有东西的总价值s除以2 让它装尽量多的东西作为第二份 剩下的就是第一份了

题目有个小坑点 是以负数作为结束条件的 不是-1 还有不要开始把s/=2 后来第一份又用s/*2-d[s] 因为s/2/*2不一定等于s了

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

<span style="font-family:Arial Black;">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55,  V = 255000;
int d[V], val[N], num[N];
int main()
{
    int n;
    while (scanf ("%d", &n),n>0)
    {
        int s = 0;
        memset(d,0,sizeof(d));
        for (int i = 1; i <= n; ++i)
        {
            scanf ("%d%d", &val[i], &num[i]);
            s += val[i] * num[i];
        }
        
        for (int i = 1; i <= n; ++i)
        {
            for (int k = 1; k<=num[i]; k *=2)
            {
                num[i] -= k;
                for (int j = s / 2; j >= k * val[i]; --j)
                    d[j] = max (d[j], d[j - k * val[i]] + k * val[i]);
            }
            if (num[i] != 0)
                for (int j = s / 2; j >= num[i] * val[i]; --j)
                    d[j] = max (d[j], d[j - num[i] * val[i]] + num[i] * val[i]);
        }
        printf ("%d %d\n", s - d[s/2], d[s/2]);
    }
    return 0;
}
</span>

中文题目就不用解释了 就是裸的二维完全背包

d[i][j]表示消耗i忍耐杀j个怪最多可获得的经验 然后就用完全背包来做了 二维背包背包不过是多了一重循环

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

<span style="font-family:Arial Black;">#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int main()
{
    //还需的经验值n，保留的忍耐度m，怪的种数k,最多的杀怪数s
    int n, m, k, s, d[N][N], exp[N], cos[N];
    while (~scanf ("%d%d%d%d", &n, &m, &k, &s))
    {
        memset (d, 0, sizeof (d));
        for (int i = 1; i <= k; ++i)
            scanf ("%d%d", &exp[i], &cos[i]);

        for (int u = 1; u <= k; ++u)
            for (int i = cos[u]; i <= m; ++i)
                for (int j = 1; j <= s; ++j)
                    d[i][j] = max (d[i][j], d[i - cos[u]][j - 1] + exp[u]);

        int i;
        for (i = 1; i <= m; ++i)
            if (d[i][s] >= n) break;
        if (i <= m) printf ("%d\n", m - i);
        else printf ("-1\n");
    }
    return 0;
}
</span>

FATE

Problem Description

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
Input

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
Output

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。
Sample Input

10 10 1 10 1 1 10 10 1 9 1 1 9 10 2 10 1 1 2 2
Sample Output

0 -1 1

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2577

题意 给你一个由大写字母和小写字母组成的字符串 模拟键盘输入的最少按键次数

直接模拟每个字符的输入 flag表示capslock的状态 1表示打开 0为关闭 开始是和输入完毕都是关闭的关闭的 用plu记录shift和capslock的按键次数

当接下来输入的字母有连续n个跟capslock状态不同时 分析可只 只有n=1时适合用shift键

如flag=1 n=1 输入a时 shift+a=2 而capslock+a+capslock=3

n>=2 如输入ab是 shift+a+shift+b=4 capslock+a+b+capslock=4

所以每次输入的字母如capslock状态不同时 就看有几个连续状态不同的字母 然后再选择用什么键

注意有一个例外当最后只有一个字母小写 capslock打开时 也应该用capslock 因为最后要换位小写状态

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

#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
const int N = 105;
int main()
{
    char s[N]; int cas, t;
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%s", s + 1);
        int l = strlen (s + 1), plu = 0, flag = 0;

        for (int i = 1; i <= l; ++i)
        {
            t = 0;
            if (flag) while (islower (s[i])) ++t, ++i;
            else      while (isupper (s[i])) ++t, ++i;

            if (t > 1||(i == l + 1 && islower (s[l]) && t == 1))
                flag = !flag, ++plu, --i;
            else if (t == 1)
                ++plu, --i;
        }

        if (flag) ++plu;
        printf ("%d\n", l + plu);
    }
    return 0;
}

How to Type

Problem Description

Pirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string.
Input

The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.
Output

For each test case, you must output the smallest times of typing the key to finish typing this string.
Sample Input

3 Pirates HDUacm HDUACM
Sample Output

8 8 8

Hint The string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8. The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8 The string “HDUACM”, can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8

Super Jumping! Jumping! Jumping!

Problem Description

Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. Maybe you are a good boy, and know little about this game, so I introduce it to you now.

The game can be played by two or more than two players. It consists of a chessboard（棋盘）and some chessmen（棋子）, and all chessmen are marked by a positive integer or “start” or “end”. The player starts from start-point and must jumps into end-point finally. In the course of jumping, the player will visit the chessmen in the path, but everyone must jumps from one chessman to another absolutely bigger (you can assume start-point is a minimum and end-point is a maximum.). And all players cannot go backwards. One jumping can go from a chessman to next, also can go across many chessmen, and even you can straightly get to end-point from start-point. Of course you get zero point in this situation. A player is a winner if and only if he can get a bigger score according to his jumping solution. Note that your score comes from the sum of value on the chessmen in you jumping path.
Your task is to output the maximum value according to the given chessmen list.
Input

Input contains multiple test cases. Each test case is described in a line as follow:
N value_1 value_2 …value_N
It is guarantied that N is not more than 1000 and all value_i are in the range of 32-int.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output

For each case, print the maximum according to rules, and one line one case.
Sample Input

3 1 3 2 4 1 2 3 4 4 3 3 2 1 0
Sample Output

4 10 3

题意 求n个数字的和最大的递增子序列

基础的dp题目 令d[i]表示以第i个数字结尾的和最大的递增子序列 有d[i]=max(d[i],d[j]+a[i]) j为1到a之间的数 且a[i]>a[j]

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1005;
int a[N], d[N];
int main()
{
    int ans,n;
    while (scanf ("%d", &n), n)
    {
        ans=0;
        for (int i = 1; i <= n; ++i)
        {
            scanf ("%d", &a[i]);
            d[i]=a[i];
            for(int j=1;j<i;++j)
                if(a[i]>a[j]) d[i]=max(d[i],d[j]+a[i]);
            ans=max(ans,d[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

Bone Collector

Problem Description

Many years ago , in Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect varies of bones , such as dog’s , cow’s , also he went to the grave …
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?

Input

The first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
Output

One integer per line representing the maximum of the total value (this number will be less than 231).
Sample Input

1 5 10 1 2 3 4 5 5 4 3 2 1
Sample Output

14

裸的01背包啦啦啦啦

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int n, v, d[N], val[N], vol[N], cas;
int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        memset (d, 0, sizeof (d));
        scanf ("%d%d", &n, &v);
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &val[i]);
        for (int i = 1; i <= n; ++i)
        {
            scanf ("%d", &vol[i]);
            for (int j = v; j >= vol[i]; --j)
                d[j] = max (d[j], d[j - vol[i]] + val[i]);
        }
        printf ("%d\n", d[v]);
    }
    return 0;
}