题意 给你n种长方体 每种都有无穷个 当一个长方体的长和宽都小于另一个时 这个长方体可以放在另一个上面 要求输出这样累积起来的最大高度

因为每个长方体都有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

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
#define maxn 105  
int x[maxn], y[maxn], z[maxn], d[maxn], n;  
int dp(int i)  
{  
    if(d[i] > 0) return d[i];  
    d[i] = z[i];  
    for(int j = 1; j <= n; ++j)  
    {  
        if((x[i] > x[j] && y[i] > y[j]) || (x[i] > y[j] && y[i] > x[j]))  
            d[i] = max(d[i], dp(j) + z[i]);  
    }  
    return d[i];  
}  
  
int main()  
{  
    int a, b, c, cas = 1;  
    while (scanf("%d", &n), n)  
    {  
        n *= 3;  
        for(int i = 1; i <= n;)  
        {  
            scanf("%d%d%d", &a, &b, &c);  
            x[i] = a; y[i] = b; z[i++] = c;  
            x[i] = a; y[i] = c; z[i++] = b;  
            x[i] = b; y[i] = c; z[i++] = a;  
        }  
  
        int ans = 0;  
        memset(d, 0, sizeof(d));  
        for(int i = 1; i <= n; ++i)  
            ans = max(dp(i), ans);  
        printf("Case %d: maximum height = %d\n", cas, ans);  
  
        cas++;  
    }  
    return 0;  
}

Perhaps you have heard of the legend of the Tower of Babylon. Nowadays many details of this tale have been forgotten. So now, in line with the educational nature of this contest, we will tell you the whole story:

The babylonians had n types of blocks, and an unlimited supply of blocks of each type. Each type-i block was a rectangular solid with linear dimensions . 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 wanted to construct the tallest tower possible by stacking blocks. The problem was 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. 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 babylonians can build with a given set of blocks.

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 , and .

Input is terminated by a value of zero (0) for n.

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“

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

Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342

题意 输入一个城市的滑雪地图 你可以从高的地方滑到伤下左右低的地方 求这个城市的最长滑雪线路长度 即在一个矩阵中找出最长递减连续序列

令d[i][j]为以格子map(i,j)为起点的最长序列 则有状态转移方程d[i][j]=max{d[a][b]}+1 a,b为与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
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
#define maxn 105  
#define a i+x[k]  
#define b j+y[k]  
int ma[maxn][maxn],d[maxn][maxn],r,c,n,ans;  
int x[4]={0,0,1,-1},y[4]={-1,1,0,0};  
  
int dp(int i,int j)  
{  
    if(d[i][j]>0) return d[i][j];  
    d[i][j]=1;  
    for(int k=0;k<4;++k)  
    if((ma[i][j]>ma[a][b])&&(a>0&&a<=r)&&(b>0&&b<=c))  
    {  
        d[i][j]=max(d[i][j],dp(a,b)+1);  
    }  
    return d[i][j];  
}  
  
int main()  
{  
    char name[100];  
    scanf("%d",&n);  
    for(int cas=1;cas<=n;++cas)  
    {  
        scanf("%s%d%d",name,&r,&c);  
        for(int i=1;i<=r;++i)  
            for(int j=1;j<=c;++j)  
                scanf("%d",&ma[i][j]);  
  
        memset(d,0,sizeof(d));  
        ans=0;  
        for(int i=1;i<=r;++i)  
            for(int j=1;j<=c;++j)  
                ans=max(dp(i,j),ans);  
  
        printf("%s: %d\n",name,ans);  
    }  
    return 0;  
}

Longest Run on a Snowboard

Michael likes snowboarding. That’s not very surprising, since snowboarding is really great. The bad thing is that in order to gain speed, the area must slide downwards. Another disadvantage is that when you’ve reached the bottom of the hill you have to walk up again or wait for the ski-lift.

Michael would like to know how long the longest run in an area is. That area is given by a grid of numbers, defining the heights at those points. Look at this example:
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

One can slide down from one point to a connected other one if and only if the height decreases. One point is connected to another if it’s at left, at right, above or below it. In the sample map, a possible slide would be24-17-16-1(start at24, end at1). Of course if you would go25-24-23-…-3-2-1, it would be a much longer run. In fact, it’s the longest possible.

Input

The first line contains the number of test casesN. Each test case starts with a line containing the name (it’s a single string), the number of rowsRand the number of columnsC. After that followRlines withCnumbers each, defining the heights.Rand C won’t be bigger than100,Nnot bigger than15and the heights are always in the range from0to100.

For each test case, print a line containing the name of the area, a colon, a space and the length of the longest run one can slide down in that area.
Sample Input 2 Feldberg 10 5 56 14 51 58 88 26 94 24 39 41 24 16 8 51 51 76 72 77 43 10 38 50 59 84 81 5 23 37 71 77 96 10 93 53 82 94 15 96 69 9 74 0 62 38 96 37 54 55 82 38 Spiral 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

Sample Output
Feldberg: 7 Spiral: 25



题意 霍默辛普森吃汉堡 有两种汉堡 一中吃一个需要m分钟 另一种吃一个需要n分钟 他共有t分钟时间要我们输出他在尽量用掉所有时间的前提下最多能吃多少个汉堡 如果时间无法用完 输出他吃的汉堡数和剩余喝酒的时间

很明显的完全背包问题 求两次 一次对个数 一次对时间就行了 时间用不完的情况下就输出时间的

d1为个数的 d2为时间的 dt保存时间

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<cstring>
#include<algorithm>
#define maxn 10005
using namespace std;
int w[2],t,d1[maxn],d2[maxn],dt[maxn];
int main()
{
    while (scanf("%d%d%d",&w[0],&w[1],&t)!=EOF)
    {
        memset(d1,0x8f,sizeof(d1));
        memset(dt,0,sizeof(dt));
        memset(d2,0,sizeof(d2));
        d1[0]=0;
        for(int i=0; i<2; ++i)
            for(int j=w[i]; j<=t; ++j)
            {
                d1[j]=max(d1[j],d1[j-w[i]]+1);
                if((dt[j]<dt[j-w[i]]+w[i])||((dt[j]==dt[j-w[i]]+w[i])&&(d2[j]<d2[j-w[i]]+1)))
                {
                    dt[j]=dt[j-w[i]]+w[i];
                    d2[j]=d2[j-w[i]]+1;
                }
            }
        if(dt[t]==t)
            printf("%d\n",d1[t]);
        else
            printf("%d %d\n",d2[t],t-dt[t]);
    }
    return 0;
}

Homer Simpson Homer Simpson, a very smart guy, likes eating Krusty-burgers. It takes Homer m minutes to eat a Krusty- burger. However, there�s a new type of burger in Apu�s Kwik-e-Mart. Homer likes those too. It takes him n minutes to eat one of these burgers. Given t minutes, you have to find out the maximum number of burgers Homer can eat without wasting any time. If he must waste time, he can have beer.

Input
Input consists of several test cases. Each test case consists of three integers m, n, t (0 < m,n,t < 10000). Input is terminated by EOF.

Output
For each test case, print in a single line the maximum number of burgers Homer can eat without having beer. If homer must have beer, then also print the time he gets for drinking, separated by a single space. It is preferable that Homer drinks as little beer as possible.
Sample Input
3 5 54
3 5 55

Sample Output
18
17

题意 商畅做活动买东西 每个人每个商品只能拿一件 要拿价值尽量高的商品

很简单的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

#include<cstdio>  
#include<cstring>  
#include<algorithm>  
using namespace std;  
#define maxn 1005  
int p[maxn],w[maxn],d[maxn],pe,t,n,g;  
int main()  
{  
    scanf("%d",&t);  
    while (t--)  
    {  
        scanf("%d",&n);  
        for(int i=1;i<=n;++i)  
            scanf("%d%d",&p[i],&w[i]);  
  
        scanf("%d",&g);  
        int ans=0;  
        for(int k=1;k<=g;++k)  
            {  
                memset(d,0,sizeof(d));  
                scanf("%d",&pe);  
                for(int i=1;i<=n;++i)  
                {  
                    for(int j=pe;j>=w[i];j--)  
                        d[j]=max(d[j],d[j-w[i]]+p[i]);  
                }  
                ans+=d[pe];  
            }  
        printf("%d\n",ans);  
    }  
    return 0;  
}

SuperSale

There is a SuperSale in a SuperHiperMarket. Every person can take only one object of each kind, i.e. one TV, one carrot, but for extra low price. We are going with a whole family to that SuperHiperMarket. Every person can take as many objects, as he/she can carry out from the SuperSale. We have given list of objects with prices and their weight. We also know, what is the maximum weight that every person can stand. What is the maximal value of objects we can buy at SuperSale?

The input consists ofTtest cases. The number of them (1<=T<=1000) is given on the first line of the input file.

Each test case begins with a line containing a single integer numberNthat indicates the number of objects (1 <= N <= 1000). Then followsNlines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The secondinteger (1<=W<=30) corresponds to the weight of object. Next line contains one integer (1<=G<=100)it’s the number of people in our group. Next G lines contains maximal weight (1<=MW<=30) that can stand this i*-th*person from our family (1<=i<=G).

For every test case your program has to determine one integer. Print out the maximal value of goods which we can buy with that family.

2

3

72 17

44 23

31 24

1

26

6

64 26

85 22

52 4

99 18

39 13

54 9

4

23

20

20

26

72

514

题意 求蜜蜂在蜂巢跑行n个格子回到原点的方法数

把每个格子抽象成一个点 最多走14步 把初始位置O的坐标设为(15,15) 保围着O的6个点如下图所示 他们到O的距离都是1

每个点周围都有这样的6个点 代表相邻的格子 这6个点到中间点的距离为1 令d[k][i][j]表示 从O点走k步到达(i,j)点的方法总数 那么很容易有转移方程 d[k][i][j]=d[k-1][i-1][j-1]+d[k-1][i][j-1]+d[k-1][i+1][j]+d[k-1][i+1][j+1]+d[k-1][i][j+1]+d[k-1][i-1][j] 边界条件为d[0][15][15]=0

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

#include<cstdio>
using namespace std;
const int L = 15, X = 30, Y = 30;
int main()
{
    int d[L][X][Y]={0}, n, t;
    d[0][15][15] = 1;
    for (int k = 1; k < L; ++k)
        for (int i = 1; i < X; ++i)
            for (int j = 1; j < Y; ++j)
                d[k][i][j] = d[k - 1][i - 1][j - 1] + d[k - 1][i][j - 1] + d[k - 1][i + 1][j] +
                             d[k - 1][i + 1][j + 1] + d[k - 1][i][j + 1] + d[k - 1][i - 1][j];
    scanf ("%d", &t);
    while (t--)
    {
        scanf ("%d", &n);
        printf ("%d\n", d[n][15][15]);
    }
    return 0;
}

Honeycomb Walk

Description

A bee larva living in a hexagonal cell of a large honeycomb decides to creep for a walk. In each “step” the larva may move into any of the six adjacent cells and afternsteps, it is to end up in its original cell.

Your program has to compute, for a givenn, the number of different such larva walks.

Input

The first line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integern, where 1 ≤n≤ 14.

Output

For each test case, output one line containing the number of walks. Under the assumption 1 ≤n≤ 14, the answer will be less than 231.

Sample Input

2 2 4

Sample Output

6 90



题意 求两串数字最长公共子序列的长度

裸的lcs没啥说的

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>  
#include<algorithm>  
using namespace std;  
const int maxn=105;  
int a[maxn],b[maxn],d[maxn][maxn],na,nb;  
void lcs()  
{  
    memset(d,0,sizeof(d));  
    for(int i=1; i<=na; ++i)  
        for(int j=1; j<=nb; ++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 k=1;  
    while(scanf("%d%d",&na,&nb),na||nb)  
    {  
        for(int i=1; i<=na; ++i)  
            scanf("%d",&a[i]);  
        for(int i=1; i<=nb; ++i)  
            scanf("%d",&b[i]);  
        lcs();  
        printf("Twin Towers #%d\nNumber of Tiles : %d\n\n",k++,d[na][nb]);  
  
    }  
    return 0;  
}

The Twin Towers

Input:standard input

**Output:**standard output

Once upon a time, in an ancient Empire, there were two towers of dissimilar shapes in two different cities. The towers were built byputting circular tiles one upon another. Each of the tiles was of the same height and had integral radius. It is no wonder that though the two towers were of dissimilar shape, they had many tiles in common.

However, more than thousand years after they were built, the Emperor ordered his architects to remove some of the tiles from the two towers so that they have exactly the same shape and size, and at the same time remain as high as possible. The order of the tiles in the new towers must remain the same as they were in the original towers. The Emperor thought that, in this way the two towers might be able to stand as the symbol of harmony and equality between the two cities. He decided to name them theTwin Towers.

Now, about two thousand years later, you are challenged with an even simpler problem: given the descriptions of two dissimilar towers you are asked only to find out the number of tiles in the highest twin towers that can be built from them.

Input

The input file consists of several data blocks. Each data block describes a pair of towers.

The first line of a data block contains two integers N1 and N2 (1 <= N1, N2 <= 100) indicating the number of tiles respectively in the two towers. The next line contains N1 positive integers giving the radii of the tiles (from top to bottom) in the first tower. Then follows another line containing N2 integers giving the radii of the tiles (from top to bottom) in the second tower.

The input file terminates with two zeros for N1 and N2.

Output

For each pair of towers in the input first output the twin tower number followed by the number of tiles (in one tower) in the highest possible twin towers that can be built from them. Print a blank line after the output of each data set.****

Sample Input

7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0

Sample Output

Twin Towers /#1
Number of Tiles : 4
Twin Towers /#2
Number of Tiles : 6 

 题意 N头牛排成一列 但编号顺序是乱的 知道每头牛前面有多少头牛编号在其之前 要求输出此时队列中每头牛的编号 本题有两种做法 一是利用数据结构的树状数组 时间复杂度低但相对较复杂 也可以依次推出每头牛的编号 这里先介绍递推的 以后再介绍数据结构优化的 从后往前递推 知道第i头牛在前i头牛里面的编号 即a[i]+1 然后加上a[i]+1之前已经被确定的编号个数（也就是被i后面的牛所确定的编号） 就是第i头牛的实际编了每次算i的编号时 i+1的编号都是确定的

/#include using namespace std; /#define M 8005 /#define t a[i]+1 //t开始为i在前i头牛中的编号，后逐步推为实际编号； int main() { int sure[M]= {0},a[M],n; scanf("%d",&n); a[1]=0; for(int i=2; i<=n; i++) scanf("%d",&a[i]); for(int i=n; i>0; i--) { for(int j=1; j<=t; j++) if(sure[j]) //编号j已经被确定; a[i]++; sure[t]=1; } for(int i=1; i<=n; i++) printf("%d\n",t); return 0; }

Lost Cows
N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.
Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.
Given this data, tell FJ the exact ordering of the cows.
/* Line 1: A single integer, N
/* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot /#2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot /#3; and so on.
/* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line /#1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.
Sample Input
5 1 2 1 0 
Sample Output
2 4 5 3 1

      
    

 题意 你有f束花和v个花瓶 每束花放在不同的花瓶中都会有不同的价值 并且花的相对顺序不能改变 也就是说第i束花放在第j个花瓶中 那么第i+1朵花要放在j以后的花瓶中 令d[i][j]表示第i朵花放在第[j]个瓶子中前i朵花的最大价值 有状态转移方程 d[i][j]=max{d[i-1][1~j-1]}+val[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
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<cstdio>  
#include<cstring>  
using namespace std;  
#define M 205  
int val[M][M],d[M][M],pre[M][M],f,v,key;  
  
void print(int i,int j)  
{  
    if(pre[i][j])  
    {  
        print(i-1,pre[i][j]);  
        printf(" %d",j);  
    }  
    else  
        printf("%d",j);  
}  
  
int main()  
{  
    scanf("%d%d",&f,&v);  
    memset(d,0x8f,sizeof(d));  
  
    for(int i=1; i<=f; ++i)  
        for(int j=1; j<=v; ++j)  
            scanf("%d",&val[i][j]);  
  
    int ans=d[0][0];  
    //注意要把ans初始化为负无穷 可能所有的val都为负；这里wa了好久；  
    d[0][0]=0;  
    //0朵花价值当然为0了；  
      
    for(int i=1; i<=f; ++i)  
        for(int j=1; j<=v; ++j)  
        {  
            for(int k=0; k<j; ++k)  
                if(d[i-1][k]+val[i][j]>d[i][j])  
                {  
                    d[i][j]=d[i-1][k]+val[i][j];  
                    pre[i][j]=k;  
                }  
        }  
    for(int j=1; j<=v; ++j)  
        if(d[f][j]>ans)  
        {  
            ans=d[f][j];  
            key=j;  
        }  
    //这里要在最后一层更新ans 因为要保证所有花都放进去；  
  
    printf("%d\n",ans);  
    print(f,key);  
    printf("\n");  
  
    return 0;  
}

Little shop of flowers

PROBLEM

You want to arrange the window of your flower shop in a most pleasant way. You haveFbunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 throughV, whereVis the number of vases, from left to right so that the vase 1 is the leftmost, and the vaseVis the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 andF. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunchimust be in a vase to the left of the vase containing bunchjwheneveri<j. Suppose, for example, you have bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.

Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.

V A S E S ****

1

2

3

4

5 ****

Bunches

1 (azaleas)

7

23

-5

-24

16 ****

2 (begonias)

5

21

-4

10

23 ****

3 (carnations)

-21

5

-4

-20

20

According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4.

To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement.

ASSUMPTIONS

1 ≤F≤ 100 whereFis the number of the bunches of flowers. The bunches are numbered 1 throughF.

**

F≤V≤ 100 whereVis the number of vases.

-50£Aij£50 whereAijis the aesthetic value obtained by putting the flower bunchiinto the vasej.

Input

The first line contains two numbers:F,V.

The followingFlines: Each of these lines containsVintegers, so thatAijis given as thej’th number on the (i+1)’st line of the input file.

Output

The first line will contain the sum of aesthetic values for your arrangement.

The second line must present the arrangement as a list ofFnumbers, so that thek’th number on this line identifies the vase in which the bunchkis put.

Sample Input
3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20

Sample Output
53 2 4 5

题意 盒子a的n边都小于盒子b时 盒子a就可以放在盒子b上 求这样最多能堆多高

DAG中不固定顶点的最长路径，小白P162有讲解，d(i)=max{d(j)+1} j表示所有能装得下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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 35
int a[M][M],d[M],pre[M],k,n,m;
using namespace std;

bool Isnest(int i,int j)
{
    sort(a[i]+1,a[i]+1+n);
    sort(a[j]+1,a[j]+1+n);
    for(int u=1;u<=n;++u)
        if(a[i][u]<=a[j][u]) return 0;
    return 1;
}

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

void print(int i)
{
    if(pre[i])
    {
        print(pre[i]);
        printf(" %d",i);
    }
    else
    {
        printf("%d",i);
        return;
    }
}
int main()
{
    while (scanf("%d%d",&k,&n)!=EOF)
    {
        for(int i=1;i<=k;++i)
            for(int j=1;j<=n;++j)
            scanf("%d",&a[i][j]);
        m=0;
        memset(pre,0,sizeof(pre));
        memset(d,0,sizeof(d));
        for(int i=1;i<=k;++i)
            if(dp(i)>dp(m))
                m=i;
        printf("%d\n",d[m]);
        print(m);
        printf("\n");
    }
    return 0;
}

Background

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class’’ cousin.

The Problem

Consider an n-dimensional ``box’’ given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.

In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes such that each box nests in box ( .

A box D = ( ) nests in a box E = ( ) if there is some rearrangement of the such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).

For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.

Formally, we define nesting as follows: box D = ( ) nests in box E = ( ) if there is a permutation of such that ( ) ``fits’’ in ( ) i.e., if for all .

The Input

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)

This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The line in the sequence ( ) gives the measurements for the box.

There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).

In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

The Output

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The smallest'' or innermost’’ box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.

The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).

If there is more than one longest nesting string then any one of them can be output.

Sample Input

5 2 3 7 8 10 5 2 9 11 21 18 8 6 5 2 20 1 30 10 23 15 7 9 11 3 40 50 34 24 14 4 9 10 11 12 13 14 31 4 18 8 27 17 44 32 13 19 41 19 1 2 3 4 5 6 80 37 47 18 21 9

Sample Output

5 3 1 2 4 5 4 7 2 5 6



题意 求两段文本的最长公共子单词序列

还是最长公共子序列 只是现在是单词不是一个字母了 用字符串数组保存 还是一样的处理 注意结果的打印和输入的处理

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 105
using namespace std;
char a[M][32],b[M][32];
int d[M][M],flag[M][M],la,lb;
bool Isfirst;
void lcs()
{
    memset(d,0,sizeof(d));
    memset(flag,0,sizeof(flag));
    for(int i=1; i<=la; ++i)
        for(int j=1; j<=lb; ++j)
        {
            if(!strcmp(a[i],b[j]))
            {
                d[i][j]=d[i-1][j-1]+1;
                flag[i][j]=1;
            }
            else if(d[i-1][j]>d[i][j-1])
            {
                d[i][j]=d[i-1][j];
                flag[i][j]=2;
            }
            else
            {
                d[i][j]=d[i][j-1];
                flag[i][j]=3;
            }
        }
}
void print(int i,int j)
{
    if(i<1||j<1)
    {
        Isfirst=true;
        return;
    }
    if(flag[i][j]==1)
    {
        print(i-1,j-1);
        if(Isfirst)
        {
            printf("%s",a[i]);
            Isfirst=false;
        }
        else printf(" %s",a[i]);
    }
    else if(flag[i][j]==2)
        print(i-1,j);
    else print(i,j-1);
}
int main()
{
    char t[M];
    while(scanf("%s",a[1])!=EOF)
    {
        la=1;
        lb=0;
        bool Isfirst=true;
        while(scanf("%s",t),t[0]!='#') strcpy(a[++la],t);
        while(scanf("%s",t),t[0]!='#') strcpy(b[++lb],t);
        lcs();
        print(la,lb);
        printf("\n");
    }
    return 0;
}

In a few months the European Currency Union will become a reality. However, to join the club, the Maastricht criteria must be fulfilled, and this is not a trivial task for the countries (maybe except for Luxembourg). To enforce that Germany will fulfill the criteria, our government has so many wonderful options (raise taxes, sell stocks, revalue the gold reserves,…) that it is really hard to choose what to do.

Therefore the German government requires a program for the following task:

Two politicians each enter their proposal of what to do. The computer then outputs the longest common subsequence of words that occurs in both proposals. As you can see, this is a totally fair compromise (after all, a common sequence of words is something what both people have in mind).

Your country needs this program, so your job is to write it for us.

The input file will contain several test cases.

Each test case consists of two texts. Each text is given as a sequence of lower-case words, separated by whitespace, but with no punctuation. Words will be less than 30 characters long. Both texts will contain less than 100 words and will be terminated by a line containing a single ‘/#’.

Input is terminated by end of file.

For each test case, print the longest common subsequence of words occuring in the two texts. If there is more than one such sequence, any one is acceptable. Separate the words by one blank. After the last word, output a newline character.

die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen muessen dringend alle subventionsgesetze verbessert werden /# die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdruecklich erhoben werden dazu muessen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden /#

die einkommen der abgeordneten muessen dringend verbessert werden