题意 给你n个立方体 立方体每面都涂有颜色 当一个立方体序号小于另一个立方体且这个立方体底面的颜色等于另一个立方体顶面的颜色 这个立方体就可以放在另一个立方体上面 求这些立方体堆起来的最大高度；

每个立方体有6种放置方式 为了便于控制 个人喜欢将一个立方体分解为6个 这样每个立方体只用考虑顶面和底面d[i]表示分解后以第i个立方体为基底可以达到的最大高度 j从1到i-1枚举 当满足top[i]==bot[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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 3005;
int buf[6], d[N], pre[N], n, m, ans;
char face[6][8] = {"front", "back", "left", "right", "top", "bottom"};
struct Cube{    int wei, bot, top;  } cube[N];

void print (int i)
{
    if (pre[i])  print (pre[i]);
    printf ("%d %s\n", cube[i].wei, face[ (i - 1) % 6]);
    return;
}

int main()
{
    int cas = 0;
    while (scanf ("%d", &n), n)
    {
        for (int i = m = 1; i <= n; ++i)
        {
            for (int k = 0; k < 6; ++k)
                scanf ("%d", &buf[k]);
            for (int k = 0; k < 6; ++k)
            {
                cube[m].wei = i;
                cube[m].top = buf[k];
                cube[m++].bot = (k % 2 ? buf[k - 1] : buf[k + 1]);
            }
        }
        memset (d, 0, sizeof (d));
        memset (pre, 0, sizeof (pre));

        for (int i = ans = 1; i <= 6 * n; ++i)
            for (int j = d[i] = 1; j < i; ++j)
                if (cube[j].wei < cube[i].wei && cube[j].bot == cube[i].top && d[i] < d[j] + 1)
                {
                    d[i] = d[j] + 1;
                    pre[i] = j;
                    if (d[i] > d[ans])
                        ans = i;
                }
        if (cas) printf ("\n");
        printf ("Case #%d\n%d\n", ++cas, d[ans]);
        print (ans);
    }
    return 0;
}

In this problem you are given N colorful cubes each having a distinct weight. Each face of a cube is colored with one color. Your job is to build a tower using the cubes you have subject to the following restrictions:

The input may contain multiple test cases. The first line of each test case contains an integer N ( ) indicating the number of cubes you are given. The ith ( ) of the next N lines contains the description of the ith cube. A cube is described by giving the colors of its faces in the following order: front, back, left, right, top and bottom face. For your convenience colors are identified by integers in the range 1 to 100. You may assume that cubes are given in the increasing order of their weights, that is, cube 1 is the lightest and cube N is the heaviest.

The input terminates with a value 0 for N.

For each test case in the input first print the test case number on a separate line as shown in the sample output. On the next line print the number of cubes in the tallest tower you have built. From the next line describe the cubes in your tower from top to bottom with one description per line. Each description contains an integer (giving the serial number of this cube in the input) followed by a single whitespace character and then the identification string (front, back, left, right, top or bottom) of the top face of the cube in the tower. Note that there may be multiple solutions and any one of them is acceptable.

Print a blank line between two successive test cases.

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

Case /#1 2 2 front 3 front Case /#2 8 1 bottom 2 back 3 right 4 left 6 top 8 front 9 front 10 top

题意 要把一根长为l的木棍切成n+1段 切割的位置分别为c[1],c[2],…,c[n] 每次切割的成本为当前切割的那一段的长度 如长度100的切成两段成本为100 求完成切割的最小成本

和最优矩阵链乘那题很像 不用打印路径更简单了 在木棍上加两个点c[0]=0 c[n+1]=l d[i][j]表示把这段木棍的第i到j个点完成切割的最小成本 如果j=i+1 不需要切割 成本为0 这是边界条件 j>i+1时 可以在i和j间取一点k 那么有d[i][j]=min{d[i][k]+d[k][j]+c[j]-c[i]} 即在k处切断 这个切割的成本为c[j]-c[i]

所以有转移方程d[i][j]=min{d[i][k]+d[k][j]+c[j]-c[i]} i<k<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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55, INF = 0x3f3f3f3f;
int d[N][N], c[N];

int dp (int i, int j)
{
    if (d[i][j] < INF)  return d[i][j];
    for (int k = i+1; k < j; ++k)
        d[i][j] = min (d[i][j], dp (i, k) + dp (k , j) + c[j] - c[i]);
    return d[i][j];
}

int main()
{
    int l, n;
    while (scanf ("%d", &l), l)
    {
        scanf ("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &c[i]);
        c[++n] = l;
        memset (d, 0x3f, sizeof (d));
        for (int i = 0; i <= n-1; ++i) d[i][i+1]=0;
        printf ("The minimum cutting is %d.\n", dp (0, n));
    }
    return 0;
}

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time.

It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

The input will consist of several input cases. The first line of each test case will contain a positive numberlthat represents the length of the stick to be cut. You can assumel< 1000. The next line will contain the numbern(n< 50) of cuts to be made.

The next line consists ofnpositive numbersc**i(0 <c**i<l) representing the places where the cuts have to be done, given in strictly increasing order.

An input case withl= 0 will represent the end of the input.

You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below.

100 3 25 50 75 10 4 4 5 7 8 0

The minimum cutting is 200. The minimum cutting is 22.





题意 求给定数目矩阵的最优链乘 并输出路径

矩阵链乘在小白第二版 P277有讲解 也是经典的动态规划 有了转移方程题目就好做了 设d[i][j]为矩阵i到矩阵j的最优链乘 初始状态d[i][i]=0 k为i，j之间的一个矩阵 x[i],y[i]分别表示第i个矩阵的行和列 则有d[i][j]=min{d[i][k]+d[k+1][j]+x[i]/*y[k]/*y[j]}
感觉这题比较难的就是路径打印了 仔细观察一下结构 其实也不难 记录每个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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

#include<cstdio>  
#include<cstring>  
using namespace std;  
#define maxn 11  
#define INF 0x3f3f3f3f  
#define t dp(i,k)+dp(k+1,j)+x[i]*y[k]*y[j]  
int d[maxn][maxn],pre[maxn][maxn],x[maxn],y[maxn],n;  
int dp(int i,int j)  
{  
    if(d[i][j]<INF) return d[i][j];  
    for(int k=i; k<j; ++k)  
        if(d[i][j]>t)  
        {  
            d[i][j]=t;  
            pre[i][j]=k;  
        }  
    return d[i][j];  
}  
  
void print(int i,int j)  
{  
    int k=pre[i][j];  
    if(k)  
    {  
        printf("(");  
        print(i,k);  
        printf(" x ");  
        print(k+1,j);  
        printf(")");  
    }  
    else  
    {  
        printf("A%d",i);  
    }  
}  
  
int main()  
{  
    int k=1;  
    while(scanf("%d",&n),n)  
    {  
        memset(d,0x3f,sizeof(d));  
        memset(pre,0,sizeof(pre));  
        for(int i=1; i<=n; ++i)  
        {  
            scanf("%d%d",&x[i],&y[i]);  
            d[i][i]=0;  
        }  
        dp(1,n);  
        printf("Case %d: ",k);  
        print(1,n);  
        printf("\n");  
        k++;  
    }  
    return 0;  
}

Given two arrays A and B, we can determine the array C = A B using the standard definition of matrix multiplication:

The number of columns in the A array must be the same as the number of rows in the B array. Notationally, let’s say that rows(A) and columns(A) are the number of rows and columns, respectively, in the A array. The number of individual multiplications required to compute the entire C array (which will have the same number of rows as A and the same number of columns as B) is then rows(A)columns(B) columns(A). For example, if A is a array, and B is a array, it will take , or 3000 multiplications to compute the C array.

To perform multiplication of more than two arrays we have a choice of how to proceed. For example, if X, Y, and Z are arrays, then to compute X Y Z we could either compute (X Y) Z or X (Y Z). Suppose Xis a array, Y is a array, and Z is a array. Let’s look at the number of multiplications required to compute the product using the two different sequences:

(X Y) Z

X (Y Z)

Clearly we’ll be able to compute (X Y) Z using fewer individual multiplications.

Given the size of each array in a sequence of arrays to be multiplied, you are to determine an optimal computational sequence. Optimality, for this problem, is relative to the number of individual multiplications required.

For each array in the multiple sequences of arrays to be multiplied you will be given only the dimensions of the array. Each sequence will consist of an integer N which indicates the number of arrays to be multiplied, and then N pairs of integers, each pair giving the number of rows and columns in an array; the order in which the dimensions are given is the same as the order in which the arrays are to be multiplied. A value of zero for N indicates the end of the input. N will be no larger than 10.

Assume the arrays are named . Your output for each input case is to be a line containing a parenthesized expression clearly indicating the order in which the arrays are to be multiplied. Prefix the output for each case with the case number (they are sequentially numbered, starting with 1). Your output should strongly resemble that shown in the samples shown below. If, by chance, there are multiple correct sequences, any of these will be accepted as a valid answer.

3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0

Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))



题意 求一个序列a某一位的最长递增序列(lis)和最长递减序列(lds)中最小值的最大值

开始直接用DP写了 然后就超时了 后来看到别人说要用二分把时间复杂度优化到O(n/*logn) 果然如此 用一个栈s保存长度为i的LIS的最小尾部s[i] top为栈顶即当前LIS的长度 初始s[1]=a[1] top=1 遍历整个序列 当a[i]>s[top]时 a[i]入栈 in[i]=top 否则 在栈中查找（二分）第一个大于等于a[i]的下标pos 并替换 这样就增加了LIS增长的潜力 in[i]=pos;

in[i]表示以a[i]为尾部的LIS的长度 求lds的过程也是类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;
int a[N], in[N], de[N], s[N], m, n, top, pos;

int BinSearch (int k, int le, int ri)
{
    while (le <= ri)
    {
        m = (le + ri) >> 1;
        if (s[m] >= k) ri = m - 1;
        else le = m + 1;
    }
    return ri + 1;
}

void lis()
{
    memset (s, 0, sizeof (s));
    memset (in, 0, sizeof (in));
    s[1] = a[1];
    in[1] = top = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (s[top] < a[i])
        {
            s[++top] = a[i];
            in[i] = top;
        }
        else
        {
            pos = BinSearch (a[i], 1, top);
            s[pos] = a[i];
            in[i] = pos;
        }
    }
}

void lds()
{
    memset (s, 0, sizeof (s));
    memset (de, 0, sizeof (de));
    s[1] = a[n];
    de[n] = top = 1;
    for (int i = n - 1; i >= 1; --i)
    {
        if (s[top] < a[i])
        {
            s[++top] = a[i];
            de[i] = top;
        }
        else
        {
            pos = BinSearch (a[i], 1, top);
            s[pos] = a[i];
            de[i] = pos;
        }
    }
}

int main()
{
    while (scanf ("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; ++i)
            scanf ("%d", &a[i]);
        int ans = 1;
        lis();
        lds();
        for (int i = 1; i <= n; ++i)
        {
            if (min (de[i], in[i]) > ans)
                ans = min (de[i], in[i]);
        }
        printf ("%d\n", ans * 2 - 1);
    }
    return 0;
}

还有超时的DP版

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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10005;
int a[N],c[N],d[N],n;

int dpde(int i)
{
    if(d[i]) return d[i];
    d[i]=1;
    for(int j=i;j<=n;++j)
    {
        if(a[i]>a[j])
            d[i]=max(d[i],dpde(j)+1);
    }
    return d[i];
}

int dpin(int i)
{
    if(c[i]) return c[i];
    c[i]=1;
    for(int j=i;j>=1;--j)
    {
        if(a[i]>a[j])
            c[i]=max(c[i],dpin(j)+1);
    }
    return c[i];
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        int ans=1;
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));

        for(int i=1;i<=n;++i)
        {
            if(min(dpde(i),dpin(i))>ans)
                ans=min(d[i],c[i]);
        }

        printf("%d\n",ans*2-1);
    }
    return 0;
}

Wavio Sequence

Wavio is a sequence of integers. It has some interesting properties.

· Wavio is of odd length i.e. *L = 2/n + 1.

· The first (n+1) integers of Wavio sequence makes a strictly increasing sequence.

· The last (n+1) integers of Wavio sequence makes a strictly decreasing sequence.

· No two adjacent integers are same in a Wavio sequence.

For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as :

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1.

Here the longest Wavio sequence is : 1 2 3 4 5 4 3 2 1. So, the output will be 9.

Input

The input file contains less than 75 test cases. The description of each test case is given below: Input is terminated by end of file.

Each set starts with a postive integer, N(1<=N<=10000). In next few lines there will be N integers.

Output

For each set of input print the length of longest wavio sequence in a line.

Sample Input Output for Sample Input

10 1 2 3 4 5 4 3 2 1 10 19 1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1 5 1 2 3 4 5 **** 9 9 1

Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters’ Panel

题意 判断一个串最少可以分解为多少个对称串 一个串从左往后和从右往左是一样的 这个串就称为对沉串

令d[i]表示给定串的前i个字母至少可以分解为多少个对称串 那么对于j=1~i 若(i,j)是一个对称串 那么有 d[i]=min(d[i],d[j-1]+1) 然后就得到答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;

int d[N]; char s[N];
bool isPal (int a, int b)
{
    while (a <= b && s[a] == s[b])
        ++a, --b;
    return a >= b;
}

int main()
{
    int cas, l;
    scanf ("%d", &cas);
    for (int ca = 1; ca <= cas; ++ca)
    {
        scanf ("%s", s + 1);
        l = strlen (s + 1);
        memset (d, 0x3f, sizeof (d));
        d[0] = 0;

        for (int i = 1; i <= l; ++i)
        {
            for (int j = 1; j <= i; ++j)
                if (isPal (j, i))  d[i] = min (d[i], d[j - 1] + 1);
        }
        printf ("%d\n", d[l]);
    }
    return 0;
}

Partitioning by Palindromes

We say a sequence of characters is a palindromeif it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not.

A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups.

Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome?

For example:

Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.

3 racecar fastcar aaadbccb

1 7 3 Kevin Waugh



题意 求母串中子串出现的次数（长度不超过1后面100个0 显然要用大数了）
令a为子串 b为母串 d[i][j]表示子串前i个字母在母串前j个字母中出现的次数当a[i]==b[j]&&d[i-1][j-1]!=0时 d[i][j]=d[i-1][j-1]+d[i][j-1]
(a[i]==b[j]时 子串前i个字母在母串前j个字母中出现的次数 等于 子串前i-1个字母在母串前j-1个字母中出现的次数 加上 子串前i个字母在母串前j-1个字母中出现的次数
a[i]!=b[j]时 子串前i个字母在母串前j个字母中出现的次数 等于 子串前i个字母在母串前j-1个字母中出现的次数)
懒得写大数模版就用java交的 ;

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

import java.util.*;
import java.math.*;

public class Main {
	public static void main(String args[]) {
		BigInteger d[][] = new BigInteger[105][10005];
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while ((t--) != 0) {
			String b = in.next();
			String a = in.next();
			int la = a.length();
			int lb = b.length();

			for (int i = 0; i < la; ++i)
				for (int j = 0; j < lb; ++j)
					d[i][j] = BigInteger.ZERO;

			if (a.charAt(0) == b.charAt(0))
				d[0][0] = BigInteger.ONE;
			for (int j = 1; j < lb; ++j) {
				if (a.charAt(0) == b.charAt(j))
					d[0][j] = d[0][j - 1].add(BigInteger.ONE);
				else
					d[0][j] = d[0][j - 1];
			}

			for (int i = 1; i < la; ++i)
				for (int j = 1; j < lb; ++j) {
					if (a.charAt(i) == b.charAt(j)
							&& d[i - 1][j - 1] != BigInteger.ZERO) {
						d[i][j] = d[i][j - 1].add(d[i - 1][j - 1]);
					} else
						d[i][j] = d[i][j - 1];
				}

			System.out.println(d[la - 1][lb - 1]);

		}
		in.close();
	}
}

还有没加大数模版的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
31
32
33
34
35
36
37

#include<cstdio>
#include<cstring>
using namespace std;
char b[10005], a[105];
int d[105][10005], la, lb, t;
void dp()
{
    memset(d, 0, sizeof(d));
    for(int j = 1; j <= lb; ++j)
    {
        if(a[1] == b[j]) d[1][j] = d[1][j - 1] + 1;
        else d[1][j] = d[1][j - 1];
    }
    for(int i = 2; i <= la; ++i)
        for(int j = 1; j <= lb; ++j)
        {
            if(a[i] == b[j] && d[i - 1][j - 1])
            {
                d[i][j] = d[i][j - 1] + d[i - 1][j - 1];
            }
            else d[i][j] = d[i][j - 1];
        }
}
int main()
{
    scanf("%s", &t);
    while(t--)
    {
        scanf("%s%s", b + 1, a + 1);
        la = strlen(a + 1);
        lb = strlen(b + 1);
        dp();
        printf("%d\n", d[la][lb]);

    }
    return 0;
}

Distinct Subsequences

A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence *X = x1*x2…xm**, another sequence *Z = z1*z2…zk** is a subsequence of X if there exists a strictly increasing sequence <*i*1,*i*2, …, *ik*> of indices of X such that for all j = 1, 2, …, k, we have xij* = *zj. For example, Z* = *bcdb is a subsequence of X* =*abcbdab with corresponding index sequence < 2, 3, 5, 7 >.

In this problem your job is to write a program that counts the number of occurrences of Z in X as a subsequence such that each has a distinct index sequence.

Input

The first line of the input contains an integer N indicating the number of test cases to follow.

The first line of each test case contains a string X, composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string Z having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither Z nor any prefix or suffix of Z will have more than 10100 distinct occurrences in X as a subsequence.

Output

For each test case in the input output the number of distinct occurrences of Z in X as a subsequence. Output for each input set must be on a separate line.****

Sample Input

2
babgbag
bag
rabbbit
rabbit

Sample Output

5
3



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

和上篇博客描述的几乎是一样的 令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

题意 设计某个地方的照明系统 一共需要n种不同类型的灯泡 接着输入 每种灯泡的电压v 对应电压电源的价格k 每个灯泡的价格c 需要这种灯泡的数量l 电压低的灯泡可以用电压高的灯泡替换 每种灯泡只需要一个对应的电源 求完成这个照明系统的最少花费

比较简单的DP 容易知道 当要替换一种灯泡中的一个到令一种电压较高的灯泡时 只有全部替换这种灯泡为另一种时才可能使总花费变小 全部替换掉就省下了这种灯泡的电源花费 先把灯泡按照电压排序 那么每种灯泡都可以替换他前面的任意灯泡了 令s[i]表示前i种灯泡的总数 那么s[i]-s[j-1]表示的是第j种到第[i]种灯泡的总数

令d[i]表示前i种灯泡的最少花费 那么可以得到转移方程 d[i]=min{d[j-1]+(s[i]-s[j-1])/*c[i]+k[i]} j为1到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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;

int d[N], s[N], v[N], k[N], c[N], l[N], o[N], n;

bool cmp (int i, int j)
{
    return v[i] < v[j];
}

int main()
{
    while (~scanf ("%d", &n), n)
    {
        for (int i = 1; i <= n; ++i)
        {
            scanf ("%d%d%d%d", &v[i], &k[i], &c[i], &l[i]);
            o[i] = i;
        }
        sort (o + 1, o + n + 1, cmp);
        memset (d, 0x3f, sizeof (d));
        d[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
            s[i] = s[i - 1] + l[o[i]];
            for (int j = 1; j <= i; ++j)
                d[i] = min (d[i], d[j - 1] + (s[i] - s[j - 1]) * c[o[i]] + k[o[i]]);
        }
        printf ("%d\n", d[n]);
    }
    return 0;
}

You are given the task to design a lighting system for a huge conference hall. After doing a lot of calculation & sketching, you have figured out the requirements for an energy-efficient design that can properly illuminate the entire hall. According to your design, you need lamps ofndifferent power ratings. For some strange current regulation method, all the lamps need to be fed with the same amount of current. So, each category of lamp has a corresponding voltage rating. Now, you know the number of lamps & cost of every single unit of lamp for each category. But the problem is,you are to buy equivalent voltage sources for all the lamp categories. You can buy a single voltage source for each category (Each source is capable of supplying to infinite number of lamps of its voltage rating.) & complete the design. But the accounts section of your company soon figures out that they might be able to reduce the total system cost by eliminating some of the voltage sources & replacing the lamps of that category with higher rating lamps. Certainly you can never replace a lamp by a lower rating lamp as some portion of the hall might not be illuminated then. You are more concerned about money-saving than energy-saving. Find the minimum possible cost to design the system.

Input

Each case in the input begins with n (1<=n<=1000), denoting the number of categories. Each of the following n lines describes a category. A category is described by 4 integers -V(1<=V<=132000), the voltage rating, K (1<=K<=1000), the cost of a voltage source of this rating, C (1<=C<=10), the cost of a lamp of this rating & L (1<=L<=100), the number of lamps required in this category. The input terminateswitha test case where n = 0. This case should not be processed.

Output

For each test case, print the minimum possible cost to design the system.

Sample Input Output for Sample Input
3

100 500 10 20

120 600 8 16

220 400 7 18

0

778



题意 有A,B两种细胞 A细胞可由空生成 非空细胞链有两种增长方式 设O为原非空细胞链 则O可增长为OAB或BOA给你一个细胞链 若其是合法分裂的 要求判断最后一次分裂是哪种方式 无法得到的输出MUTANT

若给定的S是以AB结尾的 判断去掉AB的部分是否合法即可 若S是B开始A结束的 判断去掉首尾是否合法即可；

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>  
char s[10000];  
bool dp(int i, int j)  
{  
    if (i == j)  
        return s[i] == 'A' ? 1 : 0;  
    else if (s[j - 1] == 'A' && s[j] == 'B')  
        return dp(i, j - 2);  
    else if (s[i] == 'B' && s[j] == 'A')  
        return dp(i + 1, j - 1);  
    return 0;  
}  
int main()  
{  
    int t;  
    scanf("%d", &t);  
    while (t--)  
    {  
        scanf("%s", s + 1);  
        int l = strlen(s + 1);  
        if (!strcmp(s, "A"))  
            printf("SIMPLE\n");  
        else if (s[l - 1] == 'A' && s[l] == 'B' && dp(1, l - 2))  
            printf("FULLY-GROWN\n");  
        else if (s[1] == 'B' && s[l] == 'A' && dp(2, l - 1))  
            printf("MUTAGENIC\n");  
        else  
            printf("MUTANT\n");  
    }  
    return 0;  
}

A chain of connected cells of two types A and B composes a cellular structure of some microorganisms of species APUDOTDLS.

If no mutation had happened during growth of an organism, its cellular chain would take one of the following forms:

simple stage O = A fully-grown stage O = OAB mutagenic stage O = BOA

Sample notation O = OA means that if we added to chain of a healthy organism a cell A from the right hand side, we would end up also with a chain of a healthy organism. It would grow by one cell A.

A laboratory researches a cluster of these organisms. Your task is to write a program which could find out a current stage of growth and health of an organism, given its cellular chain sequence.

A integernbeing a number of cellular chains to test, and thennconsecutive lines containing chains of tested organisms.

For each tested chain give (in separate lines) proper answers:

SIMPLE for simple stage FULLY-GROWN for fully-grown stage MUTAGENIC for mutagenic stage MUTANT any other (in case of mutated organisms)

If an organism were in two stages of growth at the same time the first option from the list above should be given as an answer.

4 A AAB BAAB BAABA

SIMPLE FULLY-GROWN MUTANT MUTAGENIC

题意 给你n个小石头 和一个数组a[m] 然后两个人轮流取石头 stan先取 olive后取 他们都完美发挥 谁取完最后一个石头谁就是赢家 感觉不是很容易看出来是dp题 令d[i]表示只有i个石子时谁赢 1表示stan赢 0表示olive赢

i-a[j]表示从i个石子一次取走a[j]个还剩下的 所以有 当(i-a[j]>0&&d[i-a[j]]=0)时 d[i]=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

#include<cstdio>  
#include<cstring>  
using namespace std;  
int d[1000005],a[12],ans,n,m;  
int main()  
{  
    while(scanf("%d",&n)!=EOF)  
    {  
        scanf("%d",&m);  
        for(int i=1;i<=m;++i)  
                scanf("%d",&a[i]);  
        memset(d,0,sizeof(d));  
        for(int i=1;i<=n;++i)  
            for(int j=1;j<=m;++j)  
            {  
                if(i-a[j]>=0&&d[i-a[j]]==0)  
                {  
                    d[i]=1;  
                    break;  
                }  
            }  
        printf(d[n]?"Stan wins\n":"Ollie wins\n");  
    }  
}

Bachet’s Game

Bachet’s game is probably known to all but probably not by this name. Initially there arenstones on the table. There are two players Stan and Ollie, who move alternately. Stan always starts. The legal moves consist in removing at least one but not more thankstones from the table. The winner is the one to take the last stone.

Here we consider a variation of this game. The number of stones that can be removed in a single move must be a member of a certain set of m numbers. Among the m numbers there is always 1 and thus the game never stalls.

The input consists of a number of lines. Each line describes one game by a sequence of positive numbers. The first number isn<= 1000000 the number of stones on the table; the second number ism<= 10 giving the number of numbers that follow; the lastmnumbers on the line specify how many stones can be removed from the table in a single move.

For each line of input, output one line saying eitherStan winsorOllie winsassuming that both of them play perfectly.

20 3 1 3 8 21 3 1 3 8 22 3 1 3 8 23 3 1 3 8 1000000 10 1 23 38 11 7 5 4 8 3 13 999996 10 1 23 38 11 7 5 4 8 3 13

Stan wins Stan wins Ollie wins Stan wins Stan wins Ollie wins