数塔

Problem Description

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：
有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input

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

Sample Output

30

Solve

#include <iostream>
#define MAXN 1000
using namespace std;
int A[MAXN][MAXN];
int main(){
    int n;cin>>n;
    while(n--){
        int  t;cin>>t;
        for(int i=1;i<=t;i++){
            for(int j=1;j<=i;j++)cin>>A[i][j];
        }
        for(int i=t-1;i>0;i--){
            for(int j=1;j<=t-1;j++){
                A[i][j]=max((A[i+1][j]+A[i][j]),(A[i+1][j+1]+A[i][j]));
            }
        }
        cout<<A[1][1]<<endl;
    }
}

Common Subsequence

Problem 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, xij = 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.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. 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.
最基本的LCS模板题目

Sample Input

abcfbc abfcab
programming contest 
abcd mnp

Sample Output

4
2
0

Solve

#include <iostream>
#include <string>
#define MAXN 1000
int dp[MAXN][MAXN];
using namespace std;
void init(int a[][MAXN]){
    for(int i=0;i<MAXN;i++){
        dp[0][i]=0;
        dp[i][0]=0;
    }
}
int main(){
    string a,b;
    while (cin>>a>>b){
        init(dp);
        for(int i=1;i<=a.size();i++){
            for(int j=1;j<=b.size();j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        cout<<dp[a.size()][b.size()]<<endl;
    }
}

Constructing Roads In JGShining's Kingdom

Problem Description

JGShining's kingdom consists of 2n(n is no more than 500,000) small cities which are located in two parallel lines.

Half of these cities are rich in resource (we call them rich cities) while the others are short of resource (we call them poor cities). Each poor city is short of exactly one kind of resource and also each rich city is rich in exactly one kind of resource. You may assume no two poor cities are short of one same kind of resource and no two rich cities are rich in one same kind of resource.

With the development of industry, poor cities wanna import resource from rich ones. The roads existed are so small that they're unable to ensure the heavy trucks, so new roads should be built. The poor cities strongly BS each other, so are the rich ones. Poor cities don't wanna build a road with other poor ones, and rich ones also can't abide sharing an end of road with other rich ones. Because of economic benefit, any rich city will be willing to export resource to any poor one.

Rich citis marked from 1 to n are located in Line I and poor ones marked from 1 to n are located in Line II.

The location of Rich City 1 is on the left of all other cities, Rich City 2 is on the left of all other cities excluding Rich City 1, Rich City 3 is on the right of Rich City 1 and Rich City 2 but on the left of all other cities ... And so as the poor ones.

But as you know, two crossed roads may cause a lot of traffic accident so JGShining has established a law to forbid constructing crossed roads.

For example, the roads in Figure I are forbidden.

In order to build as many roads as possible, the young and handsome king of the kingdom - JGShining needs your help, please help him. ^_^

Input

Each test case will begin with a line containing an integer n(1 ≤ n ≤ 500,000). Then n lines follow. Each line contains two integers p and r which represents that Poor City p needs to import resources from Rich City r. Process to the end of file.

Output

For each test case, output the result in the form of sample.
You should tell JGShining what's the maximal number of road(s) can be built.

Sample Input

2
1 2
2 1
3
1 2
2 3
3 1

Sample Output

Case 1:
My king, at most 1 road can be built.

Case 2:
My king, at most 2 roads can be built.

Hint

Huge input, scanf is recommended.

Solve

LIS的模板题目

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string>
#define MAXN 500005
#define INF (0x3f3f3f)
int a[MAXN],dp[MAXN];
using namespace std;//Huge input, scan function is recommended.
int LIS(int *A,int n){
    fill(dp,dp+MAXN,INF);
    for(int i=1;i<=n;i++){
        *lower_bound(dp,dp+n,A[i])=A[i];
    }
    return lower_bound(dp,dp+n,INF)-dp;
}
int main(){
    int n;int t=1;
    while (~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            int a_in,b_in;
            scanf("%d %d",&a_in,&b_in);
            a[a_in]=b_in;
        }
        if(LIS(a,n)==1){
            printf("Case %d:\nMy king, at most %d road can be built.\n\n",t++,LIS(a,n));
        }
        else{
            printf("Case %d:\nMy king, at most %d roads can be built.\n\n",t++,LIS(a,n));
        }
    }
}

Super Jumping! Jumping! Jumping!

Problem 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

3 1 3 2
4 1 2 3 4
4 3 3 2 1
0

Sample Output

4
10
3

Solve

LIS

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
using namespace std;
int a[1010],dp[1010];
int main(){
    int n;
    while(cin>>n&&n){
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        for(int i=0;i<n;i++) dp[i]=a[i];
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+a[i]);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++) ans=max(ans,dp[i]);
        cout<<ans<<endl;
    }
    return 0;
}

To The Max(最大子矩阵的和🤩)

Problem Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

is in the lower left corner:

9 2
-4 1
-1 8

and has a sum of 15.

Input

The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Output

Output the sum of the maximal sub-rectangle.

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

Sample Output

15

Solve

这道题非常经典，要反复推敲。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[110][110];
int n,i,j,num,ans,maxn,k;
int main(){
    while(scanf("%d",&n)!= EOF){
        memset(a,0,sizeof(a));
        ans = -9999999;
        for(i = 1; i <= n; ++i){
            for(j = 1; j <= n; ++j){
                scanf("%d",&num);
                a[i][j] = a[i-1][j] + num;
            }
        }
        for(i = 1; i <= n; ++i){
            for(j = 0; j < i; ++j){
                if(i == n && j ==1)num = 1;
                maxn = a[i][1] - a[j][1];
                for(k = 2; k <= n; ++k){
                    maxn = max(a[i][k] - a[j][k],maxn+a[i][k] - a[j][k]);
                    ans = max(maxn,ans);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Bone Collector(01背包问题)

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

Solve

#include <iostream>
#include <algorithm>
#define INF (0x3f3f3f)
#define MAXN (1005)
using namespace std;
int a[MAXN],b[MAXN];//a for value,b for weight
int DP[MAXN][MAXN];
int Solver(int N_in,int V_in){
    for(int i=0;i<MAXN;i++)DP[N_in][i]=0;
    for(int i=N_in-1;i>=0;i--){
        for(int j=0;j<=V_in;j++){
            if(j<b[i]){
                DP[i][j]=DP[i+1][j];
            }else{
                DP[i][j]=max(DP[i+1][j],DP[i+1][j-b[i]]+a[i]);
            }
        }
    }
    return DP[0][V_in];
}
int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int N,V;cin>>N>>V;
        for(int j=0;j<N;j++)    cin>>a[j];
        for(int j=0;j<N;j++)    cin>>b[j];
        cout<<Solver(N,V)<<endl;
    }
}