ACM 第九天
动态规划1
动态规划问题是面试题中的热门话题,如果要求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题,并且小问题之间也存在重叠的子问题,则考虑采用动态规划。
1、LLS 最长上升子序列
2、最大子段和
3、背包
01背包
完全背包
多重背包
混合背包
分组背包
多维背包
输出方案
输出方案种数
最优方案种数
第k优数
A - Tickets
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.
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
2
2
20 25
40
1
8
Sample Output
08:00:40 am
08:00:08 am
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<cmath>
#include<stdio.h>
using namespace std;
int main()
{
int n,k;
int s[];
int d[]; int dp[];
scanf("%d",&n);
while(n--)
{
scanf("%d",&k);
for(int i=;i<=k;i++)
{
scanf("%d",&s[i]);
}
for(int i=;i<=k;i++)
{
scanf("%d",&d[i]);
}
dp[] = ;dp[] = s[];
for(int i=;i<=k;i++)
{
dp[i]=min((dp[i-]+s[i]),(dp[i-]+d[i]));
}
int h=dp[k]/+;
int m=dp[k]/%;
int s1=dp[k]%; printf("%02d:%02d:%02d am\n", h, m, s1);
}
return ;
}
B - Longest Ordered Subsequence
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
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
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
#include<stdio.h>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
int n;
int a[];
scanf("%d",&n);
int dp[];
int i;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
dp[]=dp[]=;
for(int i=;i<=n;i++)
{
int temp=;
for(int j=;j<=i-;j++)
{
if(a[j]<a[i])
{
if(temp<dp[j])
temp=dp[j];
}
}
dp[i]=temp+;
}
int sum1=dp[];
for(int i=;i<n;i++)
{
if(dp[i+]>sum1)
sum1=dp[i+];
}
printf("%d\n",sum1);
return ;
}
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.
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.
#include<stdio.h>
#include <iostream>
#include <string.h>
using namespace std; string s; int main()
{
int t,n; cin>>t;
while(t--)
{
cin>>n>>s;
int ans=;
for(int i=; i<s.size(); i++)
{
if(s[i]=='C' && s[i+]=='C' && s[i+]=='P' && s[i+]=='C')
{
ans++;
}
}
for(int i=; i<s.size(); i++)
{
if(s[i]=='C' && s[i+]=='C'&&s[i+]=='C' && s[i+]=='P' && s[i+]=='C')
{
i+=;
continue;
}
if(s[i]=='C' && s[i+]=='C'&&s[i+]=='P'&&s[i+]=='C' )
{
i+=;
continue;
} if(s[i]=='C' && s[i+]=='C' && s[i+]=='C')
{ ans++;
break;
}
if(s[i]=='C' && s[i+]=='P' && s[i+]=='C')
{ ans++;
break;
}
if(s[i]=='C' && s[i+]=='C' && s[i+]=='P')
{ ans++;
break;
}
}
cout<<ans<<endl;
}
return ;
}
You are given a string s consisting only of characters 0 and 1. A substring [l, r] of s is a string slsl + 1sl + 2... sr, 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.
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
8
11010111
4
3
111
0
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.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#define maxn 100005
using namespace std;
//最长子序列问题,求最长子序列为0时最长序列
int main()
{
int n,ans=,sum=;
string s;
int a[maxn];
map<int,int> mp;
cin>>n>>s; for(int i=; i<n; i++)
{
if(s[i]=='')
{
a[i+]=-;
}
else if(s[i]=='')
{
a[i+]=;
}
}
for(int i=; i<=n; i++)
{
sum+=a[i];
if(mp[sum])
{
ans=max(ans,i-mp[sum]);////如果之前存在过这个和,现在又出现了,说明这个区间1,0个数是相同的,相减为长度
}
else mp[sum]=i;
if(sum==)
ans=max(ans,i);
}
cout<<ans<<endl;
return ;
}
最新文章
- Oracle_数据处理
- 【转】jquery 中scrollTop在Firefox下不起作用
- JAVA 学习随笔 : JDK Enhancement Process JEP process
- JavaScript学习笔记-正则表达式(RegExp对象)
- 我总结的js性能优化的小知识
- 大话JS面向对象之扩展篇 面向对象与面向过程之间的博弈论(OO Vs 过程)------(一个简单的实例引发的沉思)
- 1491: [NOI2007]社交网络 - BZOJ
- HDU5479 Colmerauer 单调栈+暴力优化
- asp.net后台获取前台的样式和后台给前台设置样式
- [转贴]Eclipse IDE for c++配置
- 请求接口获取到的数据其中出现null值,处理的时候导致了程序crash,解决方案如下:
- ref与out之间的区别整理 摘自与望楼http://blog.csdn.net/xiaoning8201/article/details/6893154
- Android 执行 adb shell 命令
- jqery对于select级联操作
- mysql windows 安装 错误
- c++函数集锦
- Cron任务调度CronNET
- Java并发编程快速学习
- HDU 3277 Marriage Match III(并查集+二分答案+最大流SAP)拆点,经典
- Git -- 工作区 和 暂存区