ACM 第九天

动态规划1

动态规划问题是面试题中的热门话题，如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。

1、LLS 最长上升子序列

2、最大子段和

3、背包

01背包

完全背包

多重背包

混合背包

分组背包

多维背包

输出方案

输出方案种数

最优方案种数

第k优数

A - Tickets

Jesus, what a great movie! Thousands of people are rushing to the cinema. However, this is really a tuff time for Joe who sells the film tickets. He is wandering when could he go back home as early as possible.
A good approach, reducing the total time of tickets selling, is let adjacent people buy tickets together. As the restriction of the Ticket Seller Machine, Joe can sell a single ticket or two adjacent tickets at a time.
Since you are the great JESUS, you know exactly how much time needed for every person to buy a single ticket or two tickets for him/her. Could you so kind to tell poor Joe at what time could he go back home as early as possible? If so, I guess Joe would full of appreciation for your help.

InputThere are N(1<=N<=10) different scenarios, each scenario consists of 3 lines:
1) An integer K(1<=K<=2000) representing the total number of people;
2) K integer numbers(0s<=Si<=25s) representing the time consumed to buy a ticket for each person;
3) (K-1) integer numbers(0s<=Di<=50s) representing the time needed for two adjacent people to buy two tickets together.
OutputFor every scenario, please tell Joe at what time could he go back home as early as possible. Every day Joe started his work at 08:00:00 am. The format of time is HH:MM:SS am|pm.
Sample Input

Sample Output

08:00:40 am
08:00:08 am

 1 #include<cstring>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<stdlib.h>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<stdio.h>
 9 using namespace std;
10 int main()
11 {
12     int n,k;
13     int s[2010];
14     int d[2010]; int dp[2010];
15     scanf("%d",&n);
16     while(n--)
17     {
18         scanf("%d",&k);
19         for(int i=1;i<=k;i++)
20         {
21             scanf("%d",&s[i]);
22         }
23         for(int i=2;i<=k;i++)
24         {
25             scanf("%d",&d[i]);
26         }
27         dp[0] = 0;dp[1] = s[1];
28          for(int i=2;i<=k;i++)
29          {
30              dp[i]=min((dp[i-1]+s[i]),(dp[i-2]+d[i]));
31          }
32           int h=dp[k]/3600+8;
33           int m=dp[k]/60%60;
34           int s1=dp[k]%60;
35 
36         printf("%02d:%02d:%02d am
", h, m, s1);
37     }
38     return 0;
39 }

B - Longest Ordered Subsequence

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

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 using namespace std;
 5 int main()
 6 {
 7     int n;
 8     int a[1100];
 9     scanf("%d",&n);
10     int dp[100000];
11     int i;
12     for(int i=1;i<=n;i++)
13     {
14         scanf("%d",&a[i]);
15     }
16     dp[0]=dp[1]=1;
17     for(int i=2;i<=n;i++)
18     {
19         int temp=0;
20         for(int j=1;j<=i-1;j++)
21         {
22             if(a[j]<a[i])
23             {
24                 if(temp<dp[j])
25                 temp=dp[j];
26             }
27         }
28         dp[i]=temp+1;
29     }
30     int sum1=dp[0];
31     for(int i=1;i<n;i++)
32     {
33         if(dp[i+1]>sum1)
34             sum1=dp[i+1];
35     }
36     printf("%d
",sum1);
37     return 0;
38 }

A - 难度系数 ==1

ZOJ - 3985

BaoBao has just found a string $of length consisting of 'C' and 'P' in his pocket. As a big fan of the China Collegiate Programming Contest, BaoBao thinks a substring of is "good", if and only if'C', and'P', where denotes the -th character in string . The value of is the number of different "good" substrings in . Two "good" substrings and are different, if and only if .$

To make this string more valuable, BaoBao decides to buy some characters from a character store. Each time he can buy one 'C' or one 'P' from the store, and insert the character into any position in $. But everything comes with a cost. If it's the -th time for BaoBao to buy a character, he will have to spend units of value.$

The final value BaoBao obtains is the final value of $minus the total cost of all the characters bought from the store. Please help BaoBao maximize the final value.$

Input

There are multiple test cases. The first line of the input contains an integer $, indicating the number of test cases. For each test case:$

The first line contains an integer $(), indicating the length of string .$

The second line contains the string $() consisting of 'C' and 'P'.$

It's guaranteed that the sum of $over all test cases will not exceed .$

Output

For each test case output one line containing one integer, indicating the maximum final value BaoBao can obtain.

Sample Input

3
3
CCC
5
CCCCP
4
CPCP

Sample Output

1
1
1

Hint

For the first sample test case, BaoBao can buy one 'P' (cost 0 value) and change $to "CCPC". So the final value is 1 - 0 = 1.$

For the second sample test case, BaoBao can buy one 'C' and one 'P' (cost 0 + 1 = 1 value) and change $to "CCPCCPC". So the final value is 2 - 1 = 1.$

For the third sample test case, BaoBao can buy one 'C' (cost 0 value) and change $to "CCPCP". So the final value is 1 - 0 = 1.$

It's easy to prove that no strategies of buying and inserting characters can achieve a better result for the sample test cases.

 1 #include<stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 string s;
 7 
 8 int main()
 9 {
10     int t,n;
11 
12     cin>>t;
13     while(t--)
14     {
15         cin>>n>>s;
16         int ans=0;
17         for(int i=0; i<s.size(); i++)
18         {
19             if(s[i]=='C' && s[i+1]=='C' && s[i+2]=='P' && s[i+3]=='C')
20             {
21                 ans++;
22             }
23         }
24         for(int i=0; i<s.size(); i++)
25         {
26             if(s[i]=='C' && s[i+1]=='C'&&s[i+2]=='C' && s[i+3]=='P' && s[i+4]=='C')
27             {
28                 i+=3;
29                 continue;
30             }
31             if(s[i]=='C' && s[i+1]=='C'&&s[i+2]=='P'&&s[i+3]=='C' )
32             {
33                 i+=2;
34                 continue;
35             }
36 
37             if(s[i]=='C' && s[i+1]=='C' && s[i+2]=='C')
38             {
39 
40                 ans++;
41                 break;
42             }
43             if(s[i]=='C' && s[i+1]=='P' && s[i+2]=='C')
44             {
45 
46                 ans++;
47                 break;
48             }
49             if(s[i]=='C' && s[i+1]=='C' && s[i+2]=='P')
50             {
51 
52                 ans++;
53                 break;
54             }
55         }
56         cout<<ans<<endl;
57     }
58     return 0;
59 }

B - 难度系数！=1

CodeForces - 873B

You are given a string s consisting only of characters 0 and 1. A substring [l, r] of s is a string s_ls_l + 1s_l + 2... s_r, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest balanced substring of s.

Input

The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.

The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.

Output

If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.

Examples

Input

8
11010111

Output

Input

3
111

Output

Note

In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.

In the second example it's impossible to find a non-empty balanced substring.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <map>
 5 #define maxn 100005
 6 using namespace std;
 7 //最长子序列问题,求最长子序列为0时最长序列
 8 int main()
 9 {
10     int n,ans=0,sum=0;
11     string s;
12     int a[maxn];
13     map<int,int> mp;
14     cin>>n>>s;
15 
16     for(int i=0; i<n; i++)
17     {
18         if(s[i]=='0')
19         {
20             a[i+1]=-1;
21         }
22         else if(s[i]=='1')
23         {
24             a[i+1]=1;
25         }
26     }
27     for(int i=1; i<=n; i++)
28     {
29         sum+=a[i];
30         if(mp[sum])
31         {
32             ans=max(ans,i-mp[sum]);////如果之前存在过这个和，现在又出现了，说明这个区间1，0个数是相同的，相减为长度
33         }
34         else mp[sum]=i;
35         if(sum==0)
36             ans=max(ans,i);
37     }
38     cout<<ans<<endl;
39     return 0;
40 }