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

【 题集 】 寒假计划——DP(入门)

2019年02月19日 ⁄ 综合 ⁄ 共 8609字 ⁄ 字号 评论关闭

    链接:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70533#overview

   

A - poj1837

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

Description

Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance. 
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25.
Gigel may droop any weight of any hook but he is forced to use all the weights. 
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced. 

Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device. 
It is guaranteed that will exist at least one solution for each test case at the evaluation. 

Input

The input has the following structure: 
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20); 
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis
(when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the
hook is attached: '-' for the left arm and '+' for the right arm); 
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values. 

Output

The output contains the number M representing the number of possibilities to poise the balance.

Sample Input

2 4	
-2 3 
3 4 5 8

Sample Output

2

    这题要理解题意,意思是有n个 挂钩,m个砝码,要求挂上所有的砝码,使得左右两边平衡,对于左右两端的正负,我们可以全部正数化。

    

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

#define N 30
int a[N];
int b[N];
int dp[N][15100];// 放置i个砝码,使得值为j 的方法数,正数化之后,去最后的dp[n][7500].

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

        dp[0][7500] = 1;

        for(int i = 1; i <= m; i ++)
        {
            for(int k = 1; k <= n; k ++)
            {
                for(int j = a[k]*b[i] ; j <= 15000; j ++)
                {
                    int tmp_1 = dp[i - 1][j - a[k]*b[i]];
                    if(tmp_1 > 0)
                    {
                        dp[i][j] += tmp_1;
                    }
                }
            }
        }
        printf("%d\n", dp[m][7500]);
    }
    return 0;
}

B - poj1276

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

Description

A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply
of nk bills. For example, 

N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10 

means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each. 

Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine. 

Notes: 
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc. 

Input

The program input is from standard input. Each data set in the input stands for a particular transaction and has the format: 

cash N n1 D1 n2 D2 ... nN DN 

where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers
in the input. The input data are correct. 

Output

For each set of data the program prints the result to the standard output on a separate line as shown in the examples below. 

Sample Input

735 3  4 125  6 5  3 350
633 4  500 30  6 100  1 5  0 1
735 0
0 3  10 100  10 50  10 10

Sample Output

735
630
0
0

Hint

The first data set designates a transaction where the amount of cash requested is @735. The machine contains 3 bill denominations: 4 bills of @125, 6 bills of @5, and 3 bills of @350. The machine can deliver the exact amount of requested cash. 

In the second case the bill supply of the machine does not fit the exact amount of cash requested. The maximum cash that can be delivered is @630. Notice that there can be several possibilities to combine the bills in the machine for matching the delivered
cash. 

In the third case the machine is empty and no cash is delivered. In the fourth case the amount of cash requested is @0 and, therefore, the machine delivers no cash.

 

    简单的多重背包

    

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

#define N 100010

int dp[N];
int c[N];

int cash, n;

int main()
{
    int sum, price;
    while(~scanf("%d%d",&cash,&n))
    {
        int cnt = 1;
        for(int i = 0; i < n; i ++)
        {
            scanf("%d%d",&sum,&price);
            int t = 1;
            while(sum >= t)
            {
                c[cnt ++] = t * price;
                sum = sum - t;
                t = t << 1;
            }
            if(sum)
            {
                c[cnt ++] = sum * price;
            }

        }
        if(cash == 0 || n == 0)
        {
            printf("0\n");
            continue;
        }
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i < cnt; i ++)
        {
            for(int j = cash; j >= c[i]; j --)
            {
                dp[j] = max(dp[j], dp[j - c[i]] + c[i]);
            }
        }
        printf("%d\n", dp[cash]);
    }
}

 

    

F - poj2533

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

Description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence ( a1a2, ..., aN)
be any sequence (ai1ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= 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

4

    最长上升子序列,模版题

   

#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);
    }
}

    

G - poj3176

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

Description

The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 0..99), though, and line up in a standard bowling-pin-like triangle like this: 

          7 

 3   8 

 8   1   0 

 2   7   4   4 

 4   5   2   6   5

Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest
score wins that frame. 

Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable.

Input

Line 1: A single integer, N 

Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle.

Output

Line 1: The largest sum achievable using the traversal rules

Sample Input

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

Sample Output

30

Hint

Explanation of the sample: 

          7 
         *

 3   8 
       *

 8   1   0 
       *

 2   7   4   4 
       *

 4   5   2   6   5

The highest score is achievable by traversing the cows as shown above.

    这题就是数塔问题,一般都是入门DP 的第一道题吧, 我也只会这个、、、 - -b

    

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

#define N 400

int tt[N][N];

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

    

I - poj1159

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

Description

A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order
to obtain a palindrome. 

As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome. 

Input

Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from 'A' to 'Z', lowercase letters
from 'a' to 'z' and digits from '0' to '9'. Uppercase and lowercase letters are to be considered distinct.

Output

Your program is to write to standard output. The first line contains one integer, which is the desired minimal number.

Sample Input

5
Ab3bd

Sample Output

2	

    其实就是lcs,求出lcs之后,答案就为n - lcs,但是这里需要动态数组的优化,不然内存会不够

    

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

#define N 5005
int dp[2][N];
char s1[N];
char s2[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        scanf("%s",s1);
        for(int i = 0; i < n; i ++)
        {
            s2[i] = s1[n - i - 1];
        }
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                if(s1[i - 1] == s2[j - 1])
                {
                    dp[i%2][j] = dp[(i - 1)%2][j - 1] + 1;
                }
                else
                    dp[i%2][j] = max(dp[(i-1)%2][j],dp[i%2][j-1]);
            }
        }
        printf("%d\n", n - dp[n%2][n]);
    }
}

    

抱歉!评论已关闭.