【题集】【kuangbin带你飞】专题十二基础DP1

现在的位置: 首页 > 综合 > 正文

【题集】【kuangbin带你飞】专题十二基础DP1

2019年02月19日 ⁄ 综合 ⁄ 共 10768字 ⁄ 字号小中大 ⁄ 评论关闭

B - Ignatius and the Princess IV

Time Limit:1000MS Memory Limit:32767KB 64bit IO Format:%I64d
& %I64

Description

"OK, you are not too bad, em... But you can never pass the next test." feng5166 says.

"I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers." feng5166 says.

"But what is the characteristic of the special integer?" Ignatius asks.

"The integer will appear at least (N+1)/2 times. If you can't find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha....." feng5166 says.

Can you find the special integer for Ignatius?

Input

The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the
N integers. The input is terminated by the end of file.

Output

For each test case, you have to output only one line which contains the special number you have found.

Sample Input

 5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

Sample Output

 3
5
1

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

#define N 1000010

int n;
int tt[N];

int main()
{
    int t;
    while(~scanf("%d",&n))
    {
        memset(tt, 0, sizeof(tt));
        int ans = 0;
        for(int i = 0; i < n; i ++)
        {
            scanf("%d",&t);
            tt[t] ++;
            if(tt[t] >= (n + 1)/2)
                ans = max(ans, t);
        }
        printf("%d\n", ans);
    }
}

E - Super
Jumping! Jumping! Jumping!

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64

Description

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

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

Input

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

Output

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

Sample Input

Sample Output

 4
10
3

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

#define N 1010

int tt[N];
int dp[N];

int main()
{
    int n;
    while(~scanf("%d",&n), n)
    {
        memset(dp, 0, sizeof(dp));

        for(int i = 0; i < n; i ++)
        {
            scanf("%d",&tt[i]);
        }

        dp[0] = tt[0];
        int ans = tt[0];

        for(int i = 1; i < n; i ++)
        {
            dp[i] = tt[i];
            for(int j = 0; j < i; j ++)
            {
                if(tt[j] < tt[i])
                {
                    dp[i] = max(dp[i],dp[j] + tt[i]);
                }
            }
            if(ans < dp[i])
                ans = dp[i];
        }
        printf("%d\n", ans);
    }
}

F - Piggy-Bank

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64

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

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.

恰好装满的背包问题，最后判断一下就可以了

#include <stdio.h>

const int N = 550;
int c[N];
int w[N];
int dp[10010];
const int INF = 10000000; 

int min(int x, int y)
{
	return x < y ? x : y ;
}

int main()
{
	int n, m;
	int i, j;
	int a, b;
	int cc, ww;
	while(~scanf("%d",&n))
	{
		while(n --)
		{
            scanf("%d%d", &cc, &ww);
            scanf("%d", &m);
            for(i = 0; i <= ww - cc; i ++)
            	dp[i] = INF;
            for(i = 0; i < m; i ++)
            	scanf("%d%d",&c[i], &w[i]);
			dp[0] = 0;
            for(i = 0;i < m; i ++)
            {
            	for(j = w[i]; j <= ww - cc; j ++)
            		dp[j] = min(dp[j - w[i]] + c[i], dp[j]);
            }
            if(dp[ww - cc] == INF)   
            	printf("This is impossible.\n");  
        	else  
        		printf("The minimum amount of money in the piggy-bank is %d.\n",dp[ww - cc]);  
		}
	}
	return 0;
}

G - 免费馅饼

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u

Description

都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：

为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼）

Input

输入数据有多组。每组数据的第一行为以正整数n(0<n<100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0<T<100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。

Output

每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。
提示：本题的输入数据量比较大，建议用scanf读入，用cin可能会超时。

Sample Input

Sample Output

可以把它转换成数塔问题，一开始我从上往下，绕了许久！在贪心的时候，也要注意范围！！！

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

#define N 100010


int dp[N][12];

int main()
{
    int n;
    int a, t;
    while(~scanf("%d",&n), n)
    {
        memset(dp, 0, sizeof(dp));

        int maxt = 0;

        for(int i = 1; i <= n; i ++)
        {
            scanf("%d%d",&a,&t);
            maxt = max(maxt, t);
            dp[t][a + 1] ++;
        }
        for(int i = maxt - 1; i >= 0; i --)
        {
            for(int j = 1; j <= 11; j ++)
            {
                dp[i][j] += max(dp[i + 1][j], max(dp[i + 1][j + 1], dp[i + 1][j -1]));
            }
        }
        printf("%d\n", dp[0][6]);
    }
    return 0;
}

I - 最少拦截系统

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d
& %I64u

Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

 8 389 207 155 300 299 170 158 65

Sample Output

这道题想了很久，最后用贪心写的，网上有许多不同的解法，不知道是数据弱还是怎么回事。

用一个数组记录最大值，如果比它大，再取一个，到最后有几个，就是答案。

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define N 120
#define Max 1 << 29

int tt[N];
int ans[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&tt[i]);
        }

        int tmp_1 = 1;
        int cnt = 1;
        ans[1] = tt[1];

        for(int i = 2; i <= n; i ++)
        {
            bool flag = false;
            for(int j = 1; j <= cnt; j ++)
            {
                if(ans[j] > tt[i])
                {
                    ans[j] = tt[i];
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                ans[cnt + 1] = tt[i];
                cnt ++;
                //tmp_1 ++;
            }
        }
        printf("%d\n", cnt);
    }
}

L - Common Subsequence

Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d
& %I64u

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. 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 < i1,
i2, ..., ik > of indices of X such that for all j = 1,2,...,k, x _{i_j} = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find
the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

4
2
0

这题就是最长公共子序列了、

注意边界的问题！

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;

#define N 1001
#define Max 1 << 29

char str1[N];
char str2[N];
int dp[N][N];

int main()
{
    while(~scanf("%s%s",str1 ,str2 ))
    {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        memset(dp, 0, sizeof(dp));

        for(int i = 1; i <= len1; i ++)
        {
            for(int j = 1; j <= len2; j ++)
            {
                //dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

                if(str1[i - 1] == str2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        /*for(int i = 0; i < len1; i ++)
        {
            for(int j = 0; j < len2 ; j ++)
            {
                printf("%d", dp[i][j]);
            }
            printf("\n");
        }*/

        printf("%d\n", dp[len1][len2]);
    }
}

/******


abcfbc         abfcab
programming    contest
abcd           mnp
aaaaa a
aaa aaaaaa


************/

N - Longest Ordered Subsequence

Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d
& %I64u

Description

A numeric sequence of a_i is ordered if a₁ < a₂ < ... < a_N. Let the subsequence of the given numeric sequence ( a₁, a₂, ..., a_N)
be any sequence (a_i₁, a_i₂, ..., a_{i_K}), where 1 <= i₁ < i₂ < ... < i_K <= N. For example, sequence
(1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

7
1 7 3 5 9 4 8

Sample Output

最长上升序列

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define N 1010

int tt[N];
int slen[N];

void init(int n)
{
    for(int i = 1; i <= n; i ++)
    {
        slen[i] = 1;
    }
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        init(n);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d",&tt[i]);
        }
        int ans = 1;
        for(int i = 2; i <= n; i ++)
        {
            int maxn = 0;
            for(int j = 1; j <= i - 1; j ++)
            {
                if(tt[j] < tt[i] && slen[j] > maxn)
                    maxn = slen[j];
            }
            slen[i] = maxn + 1;
            if(slen[i] > ans)
                ans = slen[i];
        }
        printf("%d\n",ans);
    }
}

【上篇】Codeforces Round #294 (Div. 2)
【下篇】【题集】【kuangbin带你飞】专题十六 KMP & 扩展KMP & Manacher

作者: Vnkwxjib

该日志由 Vnkwxjib 于5年前发表在综合分类下，最后更新于 2019年02月19日.
转载请注明: 【题集】【kuangbin带你飞】专题十二基础DP1 | 学步园 +复制链接

抱歉!评论已关闭.

学步园