题意：假期你要出去旅游 你爸爸和你妈妈对你去的城市有不同的意见 为了不让他们中的任何一个不开心 你得选出同时符合两人的方案 也就是最长公共子序列 这个大白上有很详细的讲解 直接用增量法就些 注意输入数据有空格 不能用scanf读入

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 110
using namespace std;
char a[M],b[M];
int d[M][M],n,m;
void LCS()
{
    memset(d,0,sizeof(d));
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(a[i]==b[j]) d[i][j]=d[i-1][j-1]+1;
            else d[i][j]=max(d[i-1][j],d[i][j-1]);
}
int main()
{
    int t=0;
    while(gets(a+1)!=NULL,a[1]!='#')
    {
        ++t;
        gets(b+1);
        LCS();
        printf("Case #%d: you can visit at most %d cities.\n",t,d[n][m]);
    }
}

由于本题没要求打印方案 故还可用滚动数组以达到空间上的优化

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>
#define M 110
using namespace std;
char a[M],b[M];
int d[M],n,m,r,temp;
void LCS()
{
    memset(d,0,sizeof(d));
    n=strlen(a+1);
    m=strlen(b+1);
    for(int i=1; i<=n; ++i)
    {
        r=0;
        for(int j=1; j<=m; ++j)
        {
            if(a[i]==b[j]) temp=r+1;
            else temp=max(d[j],d[j-1]);
            r=d[j];
            d[j]=temp;
        }
    }
}
int main()
{
    int t=0;
    while(gets(a+1)!=NULL,a[1]!='#')
    {
        ++t;
        gets(b+1);
        LCS();
        printf("Case #%d: you can visit at most %d cities.\n",t,d[m]);
    }
}

Problem E: Vacation

The Problem

You are planning to take some rest and to go out on vacation, but you really don’t know which cities you should visit. So, you ask your parents for help. Your mother says “My son, you MUST visit Paris, Madrid, Lisboa and London. But it’s only fun in this order.” Then your father says: “Son, if you’re planning to travel, go first to Paris, then to Lisboa, then to London and then, at last, go to Madrid. I know what I’m talking about.”

Now you’re a bit confused, as you didn’t expected this situation. You’re afraid that you’ll hurt your mother if you follow your father’s suggestion. But you’re also afraid to hurt your father if you follow you mother’s suggestion. But it can get worse, because you can hurt both of them if you simply ignore their suggestions!

Thus, you decide that you’ll try to follow their suggestions in the better way that you can. So, you realize that the “Paris-Lisboa-London” order is the one which better satisfies both your mother and your father. Afterwards you can say that you could not visit Madrid, even though you would’ve liked it very much.

If your father have suggested the “London-Paris-Lisboa-Madrid” order, then you would have two orders, “Paris-Lisboa” and “Paris-Madrid”, that would better satisfy both of your parent’s suggestions. In this case, you could only visit 2 cities.

You want to avoid problems like this one in the future. And what if their travel suggestions were bigger? Probably you would not find the better way very easy. So, you decided to write a program to help you in this task. You’ll represent each city by one character, using uppercase letters, lowercase letters, digits and the space. Thus, you can have at most 63 different cities to visit. But it’s possible that you’ll visit some city more than once.

If you represent Paris with “a”, Madrid with “b”, Lisboa with “c” and London with “d”, then your mother’s suggestion would be “abcd” and you father’s suggestion would be “acdb” (or “dacb”, in the second example).

The program will read two travel sequences and it must answer how many cities you can travel to such that you’ll satisfy both of your parents and it’s maximum.

The Input

The input will consist on an arbitrary number of city sequence pairs. The end of input occurs when the first sequence starts with an “/#”character (without the quotes). Your program should not process this case. Each travel sequence will be on a line alone and will be formed by legal characters (as defined above). All travel sequences will appear in a single line and will have at most 100 cities.

The Output

For each sequence pair, you must print the following message in a line alone:
Case /#d: you can visit at most K cities. Where d stands for the test case number (starting from 1) and K is the maximum number of cities you can visit such that you’ll satisfy both you father’s suggestion and you mother’s suggestion.

Sample Input

abcd acdb abcd dacb /#

Sample Output

Case /#1: you can visit at most 3 cities. Case /#2: you can visit at most 2 cities.

© 2001 Universidade do Brasil (UFRJ). Internal Contest Warmup 2001.

很裸的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;
}

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 

题意 你要把CD上的歌录到tape上 使得剩余磁带空间最小 很容易看出是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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int s,n,val[30],d[1000005],pre[1000005];
void print(int i)
{
    if(pre[i])
    {
        print(pre[i]);
        printf("%d ",i-pre[i]);
    }
    else
    {
        printf("%d ",i);
        return;
    }
}
int main()
{
    while(scanf("%d %d",&s,&n)!=EOF)
    {
        memset(d,0,sizeof(d));
        memset(pre,0,sizeof(pre));
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&val[i]);
            for(int j=s; j>=val[i]; --j)
                if(d[j-val[i]]+val[i]>d[j])
                {
                    d[j]=d[j-val[i]]+val[i];
                    pre[j]=j-val[i];
                }
        }
        print(d[s]);
        printf("sum:%d\n",d[s]);

    }
    return 0;
}

You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tapeNminutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.

Assumptions:

Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD

Any number of lines. Each one contains valueN, (after space) number of tracks and durations of the tracks. For example from first line in sample data:N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes

Set of tracks (and durations) which are the correct solutions and string ``sum:” and sum of duration times.

5 3 1 3 4 10 4 9 8 4 2 20 4 10 5 7 4 90 8 10 23 1 2 3 4 5 7 45 8 4 10 44 43 12 9 8 2

1 4 sum:5 8 2 sum:10 10 5 4 sum:19 10 23 1 2 3 4 5 7 sum:55 4 10 12 9 8 2 sum:45

Miguel A. Revilla
2000-01-10



题意 找出一个最长的序列，满足大象的体重增加时 智商是减小的
也是基础的DP d[i]表示以第i个大象为起点的最长序列 当满足(w[i]>w[j])&&(s[i]<s[j]时 d[i]=max(d[i],dp(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
36
37
38
39
40
41
42
43
44
45
46
47
48

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

int dp(int i)
{
    if(d[i]>0) return d[i];
    d[i]=1;
    for(int j=1; j<=n; ++j)
    {
        if((w[i]>w[j])&&(s[i]<s[j]))
        {
            if(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);
    }
    else
    {
        printf("%d\n",i);
        return;
    }
}

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

Is Bigger Smarter?

The Problem

Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the IQ’s are decreasing.

The input will consist of data for a bunch of elephants, one elephant per line, terminated by the end-of-file. The data for a particular elephant will consist of a pair of integers: the first representing its size in kilograms and the second representing its IQ in hundredths of IQ points. Both integers are between 1 and 10000. The data will contain information for at most 1000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.

Say that the numbers on the i-th data line are W[i] and S[i]. 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 an elephant). If these nintegers are a[1], a[2],…, a[n] then it must be the case that
W[a[1]] < W[a[2]] < … < W[a[n]]

and

S[a[1]] > S[a[2]] > … > S[a[n]]

In order for the answer to be correct,nshould be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs 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

很水的完全背包题 大家都会的 只是要注意把小数化为整数 不然精度丢失很严重；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include<cstdio>
#include<cstring>
using namespace std;
long long d[30005];
int val[12]={10000,5000,2000,1000,500,200,100,50,20,10,5},a;
int main()
{
    double fm;
    d[0]=1;
    for(int i=0;i<11;++i)
        for(int j=val[i];j<=30000;j+=5)
            d[j]+=d[j-val[i]];
    while (scanf("%lf",&fm),a=int(fm*100+0.5))
        printf("%6.2lf%17lld\n",fm,d[a]);
    return 0;
}

New Zealand currency consists of $100, $50, $20, $10, and $5 notes and $2, $1, 50c, 20c, 10c and 5c coins. Write a program that will determine, for any given amount, in how many ways that amount may be made up. Changing the order of listing does not increase the count. Thus 20c may be made up in 4 ways: 1 20c, 2 10c, 10c+2 5c, and 4 5c.

Input will consist of a series of real numbers no greater than $300.00 each on a separate line. Each amount will be valid, that is will be a multiple of 5c. The file will be terminated by a line containing zero (0.00).

Output will consist of a line for each of the amounts in the input, each line consisting of the amount of money (with two decimal places and right justified in a field of width 6), followed by the number of ways in which that amount may be made up, right justified in a field of width 17.

0.20 2.00 0.00

0.20 4 2.00 293



Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing