The core of dynamic programming is to find the dynamic transfer equation of the event in advance. For the time being, I have only learned a few classic DP cases.

Bone Collector

Many years ago , In Teddy’s hometown there was a man who was called “Bone Collector”. This man like to collect clocks and ranges 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

// #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<cstdio> #include<queue> #include<stack> #include<set> #include<vector> using namespace std; struct Bone{ int value; int vol; }bone[1010]; int n,v; int dp[1010][1010]; int ans(){ memset(dp,0,sizeof(dp)); for(int i = 1; i <= n; i++){ for(int j = 0; j <= v; j++){ if(bone[i].vol > j){ dp[i][j] = dp[i - 1][j]; }else{ dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - bone[i].vol] + bone[i].value); } } } return dp[n][v]; } int main(){ int t = 0; cin >> t; while(t--){ cin >> n >> v; for(int i= 1; i <= n; i++){ cin >> bone[i].value; } for(int i = 1; i <= n; i++){ cin >> bone[i].vol; } cout << ans() << endl; } return 0; }

Common Subsequence

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X =

another sequence Z =

is a subsequence of X if there exists a strictly increasing sequence

of indices of X such that for all j = 1,2… ,k, xij = zj. For example, Z =

is a subsequence of X =

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. Input abcfbc abfcab programming contest abcd mnp Output 4 2 0 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0
,>
,>
,>
,>
,>

#include<iostream> #include<algorithm> #include<string> #include<string.h> #include<cstdio> #include<queue> #include<stack> #include<set> #include<vector> using namespace std; int dp[1010][1010]; string str1,str2; int lcs(){ memset(dp,0,sizeof(dp)); for(int i = 1; i <= str1.length(); i++){ for(int j = 1; j <= str2.length(); j++){ if(str1[i - 1] == str2[j - 1]){ dp[i][j] = dp[i - 1][j - 1] + 1; }else{ dp[i][j] = max(dp[i][j - 1],dp[i - 1][j]); } } } return dp[str1.length()][str2.length()]; } int main(){ while(cin >> str1 >> str2){ cout << lcs() << endl; } return 0; }

Minimum interception system

A country develops a missile interceptor system to defend itself against missile attacks from enemy countries. But the interceptor system has one drawback: although its first round can reach any altitude, each subsequent round cannot exceed the previous one. One day, radar picks up an incoming missile from an enemy country. Since the system is still in the trial phase, there is only one system, so it is possible that it will not be able to intercept all the missiles. What should I do? Get more systems! That’s easy for you to say, but what about the cost? Cost is a big issue. That’s why I’m here to help you figure out the minimum number of interceptors you need. Input Input Input several sets of data. Each set of data includes the total number of missiles (positive integers), the altitude at which the missiles fly (the altitude given by radar is a positive integer no more than 30000, separated by Spaces). The Output of each set of data corresponds to the minimum number of such missile interceptor systems to be equipped to intercept all the missiles. Sample Input 8 389 207 155 300 299 170 158 65 Sample Output 2

// #include<iostream> #include<algorithm> #include<string> #include<string.h> #include<cstdio> #include<queue> #include<stack> #include<set> #include<vector> using namespace std; const int MAXN = 10000; int n; int a[MAXN]; // int dp[MAXN]; Int lis(){int ans = 1; // dp = 1; // dp = 1; for(int i = 2; i <= n; i++){ int max = 0; For (int j = 1; j < i; J++) {if (a) [j] < a [I] && dp [j] > Max) {/ / if the previous j height > the back of the missiles I height, is a system that can be Shared here looking for him is a converse [j] < a [I] Max = dp [j]; } dp[I] = Max + 1;} dp[I] = Max + 1;} dp[I] = Max + 1; // Since each time I updates the Max set to zero, the system at the ith height (dp[I]) is incrematised each time, and if the above for example is found, then the Max is the maximum number of additional systems required except for the ith height itself. If (ans < dp[I]){// If (ans < dp[I]){// If (ans < dp[I]){// If (ans < dp[I]){// If (ans < dp[I]); If (I = dp); if (I = dp); } } return ans; } int main(){ while(cin >> n){ for(int i = 1; i <= n; i++){ cin >> a[i]; } cout << lis() << endl; } return 0; }