题意 给你一个字符序列 你每次可以从它的头部或尾部拿出一个字符组成一个新的字符序列 输出这样做能达到的最小的字符序列 每行最多输出80个字符(开始被这个坑了好久)

直接模拟就行 哪边小就选哪边 相等就往内看

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

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const int N = 30010;

int main()
{
    char s[N][2];
    int n;
    while (~scanf ("%d", &n))
    {
        string ans;
        for (int i = 1; i <= n; ++i)
            scanf ("%s", s[i]);
        int le = 1, ri = n;
        while (le <= ri)
        {
            if (le == ri)
            {
                ans += s[le][0];
                break;
            }
            int tl = le, tr = ri;
            while (s[tl][0] == s[tr][0] && le <= ri) ++tl, --tr;
            if (s[tl][0] > s[tr][0])
                ans += s[ri][0], --ri;
            else
                ans += s[le][0], ++le;
        }

        int l = ans.length();
        if (l > 80)
        {
            for (int i = 1; i <= l; ++i)
                if (i != 1 && i % 80 == 1) printf ("\n%c", ans[i - 1]);
                else printf ("%c", ans[i - 1]);
            printf ("\n");
        }
        else cout << ans << endl;
    }
    return 0;
}

Best Cow Line, Gold

Description
FJ is about to take his N (1 ≤ N ≤ 30,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 ith 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

6 A C D B C B

Sample Output

ABCBCD

题意 中文

简单的多阶段决策DP 令p[0]=0 p[n]=l d[i]表示乌龟从起点到第i个加油站所需的最小时间 那么有d[i]=min(d[i],d[j]+t(j,i)) t(j,i)表示 在第j个加油站加满油 然后直接开到第i个加油站 当然第0个加油站是起点就不用加油了 这样推到最后d[n]就是乌龟所需的最小时间了

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105,INF=999999;
double d[N],ti;
int main()
{
    int n, c, t, vr, v1, v2, l, p[N];
    while (~scanf ("%d", &l))
    {
        scanf ("%d%d%d%d%d%d", &n, &c, &t, &vr, &v1, &v2);
        ++n,p[0]=0;
        for (int i = 1; i < n; ++i)
            scanf ("%d", &p[i]); p[n] = l;

        for (int i = 1; i <= n; ++i)
        {
            d[i]=INF;
            for (int j = 0; j < i; ++j)
            {
                int len = p[i] - p[j];
                if (len > c) ti = c * 1.0 / v1 + (len - c) * 1.0 / v2;
                else ti = len * 1.0 / v1;
                if (j) ti += t;
                d[i]=min(d[i],d[j]+ti);
            }
        }

        if (d[n] < l * 1.0 / vr)
            printf ("What a pity rabbit!\n");
        else printf ("Good job,rabbit!\n");
    }
    return 0;
}

龟兔赛跑

Problem Description

据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“”小飞鸽”牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为VT2 m/s。更过分的是，乌龟竟然在跑道上修建了很多很多（N个)的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。
比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。
Input

本题目包含多组测试，请处理到文件结束。每个测试包括四行：
第一行是一个整数L代表跑道的总长度
第二行包含三个整数N，C，T，分别表示充电站的个数，电动车冲满电以后能行驶的距离以及每次充电所需要的时间
第三行也是三个整数VR，VT1，VT2，分别表示兔子跑步的速度，乌龟开电动车的速度，乌龟脚蹬电动车的速度
第四行包含了N(N<=100)个整数p1,p2…pn,分别表示各个充电站离跑道起点的距离，其中0<p1<p2<…<pn<L
其中每个数都在32位整型范围之内。
Output

当乌龟有可能赢的时候输出一行 “What a pity rabbit!”。否则输出一行”Good job,rabbit!”;
题目数据保证不会出现乌龟和兔子同时到达的情况。
Sample Input

100 3 20 5 5 8 2 10 40 60 100 3 60 5 5 8 2 10 40 60
Sample Output

Good job,rabbit! What a pity rabbit!

题意 你去打boss 开始你的蓝和血还有boss的血都是100 每秒你先打boss一下 然后boss打你一下你减少q点血 你有n个技能 第i个技能耗蓝a[i] 对boss的伤害为b[i] 普攻伤害为1 而且你每秒回复t点蓝（恢复后不超过100） 求你最少可以多少次打死boss

你最多能打100/q或者100/q+1次 令d[i][j]表示第i秒所剩蓝量为j时boss剩下的最少血量 m为j还未恢复蓝之前的蓝量 j = min (100, m + t) 那么有 d[i][j] = min (d[i][j], d[i - 1][m + a[k]] - b[k]);

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int a[N], b[N], d[N][N];
int main()
{
    int n, t, q, ans, ti;
    while (scanf ("%d%d%d", &n, &t, &q), n)
    {
        ++n;
        ti = (100 % q) ? (100 / q + 1) : (100 / q);
        a[1] = 0, b[1] = 1;
        for (int i = 2; i <= n; ++i)
            scanf ("%d%d", &a[i], &b[i]);
            
        memset (d, 0x3f, sizeof (d));
        d[0][100] = 100; ans = 0;

        for (int i = 1; i <= ti; ++i)
            for (int m = 0; m <= 100; ++m)
            {
                int j = min (100, m + t);
                for (int k = 1; k <= n; ++k)
                    if (m + a[k] <= 100)
                        d[i][j] = min (d[i][j], d[i - 1][m + a[k]] - b[k]);
                if (d[i][j] <= 0)
                {
                    ans = i, i = ti;
                    break;
                }
            }

        if (ans == 0) printf ("My god\n");
        else printf ("%d\n", ans);
    }
    return 0;
}

Warcraft

Problem Description

Have you ever played the Warcraft?It doesn’t matter whether you have played it !We will give you such an experience.There are so many Heroes in it,but you could only choose one of them.Each Hero has his own skills.When such a Skill is used ,it costs some MagicValue,but hurts the Boss at the same time.Using the skills needs intellegence,one should hurt the enemy to the most when using certain MagicValue.
Now we send you to complete such a duty to kill the Boss(So cool~~).To simplify the problem:you can assume the LifeValue of the monster is 100, your LifeValue is 100,but you have also a 100 MagicValue!You can choose to use the ordinary Attack(which doesn’t cost MagicValue),or a certain skill(in condition that you own this skill and the MagicValue you have at that time is no less than the skill costs),there is no free lunch so that you should pay certain MagicValue after you use one skill!But we are good enough to offer you a “ResumingCirclet”(with which you can resume the MagicValue each seconds),But you can’t own more than 100 MagicValue and resuming MagicValue is always after you attack.The Boss is cruel , be careful!
Input

There are several test cases,intergers n ,t and q (0<n<=100，1<=t<=5，q>0) in the first line which mean you own n kinds of skills ,and the “ResumingCirclet” helps you resume t points of MagicValue per second and q is of course the hurt points of LifeValue the Boss attack you each time(we assume when fighting in a second the attack you show is before the Boss).Then n lines follow,each has 2 intergers ai and bi(0<ai,bi<=100).which means using i skill costs you ai MagicValue and costs the Boss bi LifeValue.The last case is n=t=q=0.
Output

Output an interger min (the minimun time you need to kill the Boss)in one line .But if you die(the LifeValue is no more than 0) ,output “My god”!
Sample Input

4 2 25 10 5 20 10 30 28 76 70 4 2 25 10 5 20 10 30 28 77 70 0 0 0
Sample Output

4 My god

Hint Hint: When fighting,you can only choose one kind of skill or just to use the ordinary attack in the whole second,the ordinary attack costs the Boss 1 points of LifeValue,the Boss can only use ordinary attack which costs a whole second at a time.Good Luck To You!

题意 珠宝店到珍珠批发商进货 第i种价格为p[i]的珍珠需要n个 则珍珠的结算价格为∑(n+10)/*p[i] 由于没种珍珠的数量结算时都要加上10 所以有时候把便宜的珍珠换为贵的结算价格反而变少了 给你一张购买清单 珍珠价格是递增的 每种珍珠都可以替换为比它贵的 求最少总花费

简单dp 令d[i]表示前i种珍珠的最少花费 sum[i]表示第1种到第第i种的总数 那么有转移方程 d[i]=min{d[j-1]+(sum[i]-sum[j-1]+10)/*p[i]} (sum[i]-sum[j-1]+10)/*p[i]表示第j种到第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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int p[N], d[N], s[N],num, n, cas;
int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf ("%d%d", &num, &p[i]);
            s[i] = s[i - 1] + num;
        }
        memset(d,0x3f,sizeof(d));
        d[0]=0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                d[i] = min (d[i], d[j-1] + (s[i] - s[j - 1] + 10) * p[i]);
        printf ("%d\n", d[n]);
    }
    return 0;
}

Pearls

Problem Description

In Pearlania everybody is fond of pearls. One company, called The Royal Pearl, produces a lot of jewelry with pearls in it. The Royal Pearl has its name because it delivers to the royal family of Pearlania. But it also produces bracelets and necklaces for ordinary people. Of course the quality of the pearls for these people is much lower then the quality of pearls for the royal family. In Pearlania pearls are separated into 100 different quality classes. A quality class is identified by the price for one single pearl in that quality class. This price is unique for that quality class and the price is always higher then the price for a pearl in a lower quality class.
Every month the stock manager of The Royal Pearl prepares a list with the number of pearls needed in each quality class. The pearls are bought on the local pearl market. Each quality class has its own price per pearl, but for every complete deal in a certain quality class one has to pay an extra amount of money equal to ten pearls in that class. This is to prevent tourists from buying just one pearl.
Also The Royal Pearl is suffering from the slow-down of the global economy. Therefore the company needs to be more efficient. The CFO (chief financial officer) has discovered that he can sometimes save money by buying pearls in a higher quality class than is actually needed. No customer will blame The Royal Pearl for putting better pearls in the bracelets, as long as the prices remain the same.
For example 5 pearls are needed in the 10 Euro category and 100 pearls are needed in the 20 Euro category. That will normally cost: (5+10)/*10 + (100+10)/*20 = 2350 Euro.
Buying all 105 pearls in the 20 Euro category only costs: (5+100+10)/*20 = 2300 Euro.
The problem is that it requires a lot of computing work before the CFO knows how many pearls can best be bought in a higher quality class. You are asked to help The Royal Pearl with a computer program.
Given a list with the number of pearls and the price per pearl in different quality classes, give the lowest possible price needed to buy everything on the list. Pearls can be bought in the requested, or in a higher quality class, but not in a lower one.
Input

The first line of the input contains the number of test cases. Each test case starts with a line containing the number of categories c (1 <= c <= 100). Then, c lines follow, each with two numbers ai and pi. The first of these numbers is the number of pearls ai needed in a class (1 <= ai <= 1000). The second number is the price per pearl pi in that class (1 <= pi <= 1000). The qualities of the classes (and so the prices) are given in ascending order. All numbers in the input are integers.
Output

For each test case a single line containing a single number: the lowest possible price needed to buy everything on the list.
Sample Input

2 2 100 1 100 2 3 1 10 1 11 100 12
Sample Output

330 1344

题意 判断能否由字符串a,b中的字符不改变各自的相对顺序组合得到字符串c

本题有两种解法 DP或者DFS

考虑DP 令d[i][j]表示能否有a的前i个字符和b的前j个字符组合得到c的前i+j个字符 值为0或者1 那么有d[i][j]=(d[i-1][j]&&a[i]==c[i+j])||(d[i][j-1]&&b[i]==c[i+j]) a,b的下标都是从1开始的 注意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

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 205;
char a[N], b[N], c[2 * N];
bool  d[N][N];

int main()
{
    int cas;
    scanf ("%d", &cas);
    for (int k = 1; k <= cas; ++k)
    {
        scanf ("%s%s%s", a + 1, b + 1, c + 1);
        int la = strlen (a + 1), lb = strlen (b + 1), i = 1, j = 1;
        memset (d, 0, sizeof (d));

        while (a[i] == c[i] && i <= la)
            d[i++][0] = true;
        while (b[j] == c[j] && j <= lb)
            d[0][j++] = true;
        for (int i = 1; i <= la; ++i)
            for (int j = 1; j <= lb; ++j)
                d[i][j] = ( (d[i - 1][j] && a[i] == c[i + j]) || (d[i][j - 1] && b[j] == c[i + j]));

        printf ("Data set %d: ", k);
        printf (d[la][lb] ? "yes\n" : "no\n");
    }
    return 0;
}

下面是dfs的代码 看能否在ab中对应搜到c的每一个字母就可

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

//DFS版
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 205;
char a[N], b[N], c[2 * N];
bool vis[N][N], ans;
void dfs (int i, int j, int k)
{
    if (c[k] == '\0') ans = true;
    if (ans || vis[i][j])  return ;
    vis[i][j] = true;
    if (a[i] == c[k]) dfs (i + 1, j, k + 1);
    if (b[j] == c[k]) dfs (i, j + 1, k + 1);
}
int main()
{
    int cas;
    scanf ("%d", &cas);
    for (int ca = 1; ca <= cas; ++ca)
    {
        ans = false;
        memset (vis, 0, sizeof (vis));
        scanf ("%s%s%s", a, b, c);
        dfs (0, 0, 0);
        printf ("Data set %d: ", ca);
        printf (ans ? "yes\n" : "no\n");
    }
    return 0;
}

Zipper

Problem Description

Given three strings, you are to determine whether the third string can be formed by combining the characters in the first two strings. The first two strings can be mixed arbitrarily, but each must stay in its original order.
For example, consider forming “tcraete” from “cat” and “tree”:
String A: cat
String B: tree
String C: tcraete
As you can see, we can form the third string by alternating characters from the two strings. As a second example, consider forming “catrtee” from “cat” and “tree”:
String A: cat
String B: tree
String C: catrtee
Finally, notice that it is impossible to form “cttaree” from “cat” and “tree”.
Input

The first line of input contains a single positive integer from 1 through 1000. It represents the number of data sets to follow. The processing for each data set is identical. The data sets appear on the following lines, one data set per line.
For each data set, the line of input consists of three strings, separated by a single space. All strings are composed of upper and lower case letters only. The length of the third string is always the sum of the lengths of the first two strings. The first two strings will have lengths between 1 and 200 characters, inclusive.
Output

For each data set, print:
Data set n: yes
if the third string can be formed from the first two, or
Data set n: no
if it cannot. Of course n should be replaced by the data set number. See the sample output below for an example.
Sample Input

3 cat tree tcraete cat tree catrtee cat tree cttaree
Sample Output

Data set 1: yes Data set 2: yes Data set 3: no

题意 求一个n/*n矩阵的最大子矩阵和

HDU 1003 max sum 的升级版 把二维简化为一维就可以用1003的方法去做了 用mat[i][j]存 第i行前j个数的和 那么mat[k][j]-mat[k][i]就表示第k行 第i+1个数到第j个数的和了 再将k从一枚举到n就可以得到这个这个宽度为j-i的最大矩阵和了 然后i,j又分别从1枚举到n就能得到结果了 和1003的方法一样 只是多了两层循环

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

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105;
int main()
{
    int t, n, sum, ans, mat[N][N];
    while (~scanf ("%d", &n))
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                scanf ("%d", &t);
                mat[i][j] = mat[i][j - 1] + t;
            }
        for (int i = ans = 0; i < n; ++i)
            for (int j = i + 1; j <= n; ++j)
            {
                sum = 0;
                for (int k = 1; k <= n; ++k)
                {
                    if (sum < 0) sum = 0;
                    sum += (mat[k][j] - mat[k][i]);
                    if (sum > ans) ans = sum;
                }
            }
        printf ("%d\n", ans);
    }
    return 0;
}

To The Max

Problem Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
Input

The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output

Output the sum of the maximal sub-rectangle.
Sample Input

4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
Sample Output

15

题意 老鼠在一个小镇吃奶酪 城镇可以看成一个n/*n的矩阵 其中每个格子都有一定数量的奶酪mat[i][j] 老鼠从(0,0) 开始吃 而且下个吃的格子里的奶酪必须比上个格子多 老鼠只能水平方向或者垂直方向走 而且每次走的距离不能超过k 求老鼠最多能吃多少奶酪

起点是固定的 比较容易 直接记忆化搜索

令d[i][j]表示以(i,j)为终点的最优解 那么对于所有(i,j)能到达的点(x,y)有 d[i][j]=max(d[i][j],d[x][y]+mat[x][y]) 结果直接输出d[0][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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
#define xx i+k*x[l]
#define yy j+k*y[l]
int d[N][N], mat[N][N], m, n;
int x[4] = { -1, 1, 0, 0}, y[4] = {0, 0, -1, 1};

int dp (int i, int j)
{
    if (d[i][j] > 0) return d[i][j];
    d[i][j] = mat[i][j];
    for (int k = 1; k <= m; ++k)
        for (int l = 0; l <= 4; ++l)
        {
            if (xx > 0 && xx <= n && yy > 0 && yy <= n && mat[xx][yy] > mat[i][j])
                d[i][j] = max (d[i][j], mat[i][j] + dp (xx, yy));
        }
    return d[i][j];
}

int main()
{
    while (scanf ("%d%d", &n, &m), n > 0)
    {
        memset (d, -1, sizeof (d));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf ("%d", &mat[i][j]);
        printf ("%d\n", dp (1, 1));
    }
    return 0;
}

FatMouse and Cheese

Problem Description

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he’s going to enjoy his favorite food.
FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse – after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.
Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.
Input

There are several test cases. Each test case consists of
a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) … (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), … (1,n-1), and so on.
The input ends with a pair of -1’s.
Output

For each test case output in a line the single integer giving the number of blocks of cheese collected.
Sample Input

3 1 1 2 5 10 11 6 12 12 7 -1 -1
Sample Output

37

题意 输入n个老鼠的体重和速度 从里面找出最长的序列 是的重量递增时速度递减

简单的DP 令d[i]表示以第i个老鼠为所求序列最后一个时序列的长度 对与每个老鼠i 遍历所有老鼠j 当(w[i] > w[j]) && (s[i] < s[j])时 有d[i]=max(d[i],d[j]+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

#include<cstdio>
#include<algorithm>
using namespace std;
const int M=1005;
int w[M], s[M], d[M], pre[M], n, key;

int dp (int i)
{
    if (d[i] > 0) return d[i];
    for (int j = d[i] = 1; j <= n; ++j)
        if ( (w[i] > w[j]) && (s[i] < s[j]) && (d[i] < dp (j) + 1))
            d[i] = d[j] + 1, pre[i] = j;
    return d[i];
}

void print (int i)
{
    if (pre[i])
        print (pre[i]);
    printf ("%d\n", i);
}

int main()
{
    n = 0;
    while (scanf ("%d %d", &w[n], &s[++n]) != EOF);
    for (int i = key =1; i <= n; ++i)
        if (dp (i) > dp (key)) key = i;
    printf ("%d\n", d[key]);
    print (key);
    return 0;
}

FatMouse’s Speed

Problem Description

FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
Input

Input contains data for a bunch of mice, one mouse per line, terminated by end of file.
The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.
Two mice may have the same weight, the same speed, or even the same weight and speed.
Output

Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],…, m[n] then it must be the case that
W[m[1]] < W[m[2]] < … < W[m[n]]
and
S[m[1]] > S[m[2]] > … > S[m[n]]
In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.
Sample Input

6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900
Sample Output

4 4 5 9 7

题意 知道空存钱罐的重量和装满钱的存钱罐的重量及每种币值的重量 求存钱罐里至少有多少钱

裸的完全背包 但是是求最小值 所以初始0要变成初始INF max也要变成min

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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005, INF = 0x3f3f3f3f;
int val[N], wei[N], d[N];
int main()
{
    int cas, t, s, n;
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d%d", &t, &s);
        s -= t;
        scanf ("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf ("%d%d", &val[i], &wei[i]);
        memset (d, 0x3f, sizeof (d));
        d[0] = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = wei[i]; j <= s; ++j)
                d[j] = min (d[j], d[j - wei[i]] + val[i]);
        if (d[s] == INF) printf ("This is impossible.\n");
        else printf ("The minimum amount of money in the piggy-bank is %d.\n", d[s]);
    }
    return 0;
}

Piggy-Bank

Problem Description

Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input

The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it’s weight in grams.
Output

Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”.
Sample Input

3 10 110 2 1 1 30 50 10 110 2 1 1 50 30 1 6 2 10 3 20 4
Sample Output

The minimum amount of money in the piggy-bank is 60. The minimum amount of money in the piggy-bank is 100. This is impossible.

题意 有两行数a[n1] b[n2] 分别有n1 n2个数 当第一行一个数和第二行一个数相等时 他们就可以连起来 每个数只能连一个 求最有多少条线使得每条都至少有一条和它相交

令d[i][j]表示 a的前i个数和j的前j个数最多可以连接多少条

当a[i]==b[j]时 将们连起来是肯定不与其它线相交的 所以d[i][j]=max(d[i-1][j],d[i][j-1])

当a[i]!=b[j]时 如果可以在第一行找一个数x<i 第二行找一个数y<j 使得a[x]==b[j] b[y]==a[i] 那么有d[i][j]=max(d[x][y]+2,d[i-1][j],d[i][j-1]) 如果找不到d[i][j]=max(d[i-1][j],d[i][j-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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 105;
int a[N], b[N], d[N][N], la, lb, cas;
int main()
{
    scanf ("%d", &cas);
    while (cas--)
    {
        scanf ("%d%d", &la, &lb);
        for (int i = 1; i <= la; ++i)
            scanf ("%d", &a[i]);
        for (int j = 1; j <= lb; ++j)
            scanf ("%d", &b[j]);

        for (int i = 1; i <= la; ++i)
            for (int j = 1; j <= lb; ++j)
            {
                d[i][j] = max (d[i][j - 1], d[i - 1][j]);
                int x, y;
                for (x = i - 1; x >= 1; --x)
                    if (a[x] == b[j]) break;
                for (y = j - 1; y >= 1; --y)
                    if (a[i] == b[y]) break;

                if (x && y && a[i] != b[j])
                    d[i][j] = max (d[x - 1][y - 1] + 2, d[i][j]);
            }

        printf ("%d\n", d[la][lb]);
    }
    return 0;
}

Crossed Matchings

Description
There are two rows of positive integer numbers. We can draw one line segment between any two equal numbers, with values r, if one of them is located in the first row and the other one is located in the second row. We call this line segment an r-matching segment. The following figure shows a 3-matching and a 2-matching segment.
We want to find the maximum number of matching segments possible to draw for the given input, such that:

1. Each a-matching segment should cross exactly one b-matching segment, where a != b .
2. No two matching segments can be drawn from a number. For example, the following matchings are not allowed. Write a program to compute the maximum number of matching segments for the input data. Note that this number is always even.

Input

The first line of the input is the number M, which is the number of test cases (1 <= M <= 10). Each test case has three lines. The first line contains N1 and N2, the number of integers on the first and the second row respectively. The next line contains N1 integers which are the numbers on the first row. The third line contains N2 integers which are the numbers on the second row. All numbers are positive integers less than 100.

Output

Output should have one separate line for each test case. The maximum number of matching segments for each test case should be written in one separate line.

Sample Input

3 6 6 1 3 1 3 1 3 3 1 3 1 3 1 4 4 1 1 3 3 1 1 3 3 12 11 1 2 3 3 2 4 1 5 1 3 5 10 3 1 2 3 2 4 12 1 5 5 3

Sample Output

6 0 8