2014
03-23

# Pie

A lot of boys and girls come to our company to pie friends. After we get their information, we need give each of them an advice for help. We know everyone’s height, and we believe that the less difference of a girl and a boy has, the better it is. We need to find as more matches as possible, but the total difference of the matches must be minimum.

The input consists of multiple test cases. The first line of each test case contains two integers, n, m (0 < n, m <= 10000), which are the number of boys and the number of girls. The next line contains n float numbers, indicating the height of each boy. The last line of each test case contains m float numbers, indicating the height of each girl. You can assume that |n � m| <= 100 because we believe that there is no need to do with that if |n � m| > 100. All of the values of the height are between 1.5 and 2.0.
The last case is followed by a single line containing two zeros, which means the end of the input.

The input consists of multiple test cases. The first line of each test case contains two integers, n, m (0 < n, m <= 10000), which are the number of boys and the number of girls. The next line contains n float numbers, indicating the height of each boy. The last line of each test case contains m float numbers, indicating the height of each girl. You can assume that |n � m| <= 100 because we believe that there is no need to do with that if |n � m| > 100. All of the values of the height are between 1.5 and 2.0.
The last case is followed by a single line containing two zeros, which means the end of the input.

2 3
1.5 2.0
1.5 1.7 2.0
0 0

0.000000

HDU 2577

# How to Type

http://acm.hdu.edu.cn/showproblem.php?pid=2577

dp[2][i],表示到第i个字母的时候最少敲击的次数.

dp[1]表示CapsLock开着的情况，在这种情况下要输入小写字母至少2下，大写字则为1下

dp[0]表示CapsLock关闭的情况，在这种情况下输入小写字母至少1下，大写字母则为2下

if(islower(str[i))

dp[0][i]=min(dp[0][i-1]+1,dp[1][i-1]+2);    //在CapsLock关闭的状态，小写字母按1下，大写按2下，后面一样分析.

dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+2);

else

dp[0][i]=min(dp[0][i-1]+2,dp[1][i-1]+2);

dp[1][i]=min(dp[0][i-1]+2,dp[1][i-1]+1);

HDU 1513

Palindrome

http://acm.hdu.edu.cn/showproblem.php?pid=1513

LCS的一般转移方程是

if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;

else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

pre          dp[i-1][j]

1-pre      dp[i][j-1]      dp[i][j]

#include <cstdio>
#include <memory.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int N;
char a[2][5555];
int dp[2][5555];
while(scanf("%d",&N)!=EOF){
scanf("%s",a[0]);
for(int i=0;a[0][i];i++){
a[1][N-i-1]=a[0][i];
}
a[1][N]='/0';                                                                   //a[1]是a[0]的反串
memset(dp,0,sizeof(dp));
int pre=0;
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(a[0][i-1]==a[1][j-1]){                                              //1-pre表示现在的，pre表示之前的，s1[i]==s2[i]，那么现在的就等于之前的+1
dp[1-pre][j]=dp[pre][j-1]+1;
}
else{
dp[1-pre][j]=max(dp[pre][j],dp[1-pre][j-1]);       //不相等则由之前的j或者现在的j-1继承过来
}
}
pre^=1;
}
printf("%d/n",N-dp[pre][N]);
}
return 0;
}

HDU 1025

# Constructing Roads In JGShining’s Kingdom

http://acm.hdu.edu.cn/showproblem.php?pid=1025

1 4 3 5 4

#include <iostream>
#include <cstdio>
#define inf 500002
using namespace std;
int dp[inf];
int p[inf];
int main(){
int N;
int a,b;
int cas=0;
while(scanf("%d",&N)!=EOF){
for(int i=1;i<=N;i++){
scanf("%d%d",&a,&b);
p[a]=b;
}
dp[1]=p[1];
int up,low,mid;
int len=1;
for(int i=1;i<=N;i++){                         //这里是核心代码
low=1;up=len;				      //2分找到a[i]应该插入的位置，也就是说dp[low]是指长度为low的最后一个值的最小指
while(low<=up){
mid = (low+up)/2;
if(dp[mid]>=p[i])
up = mid-1;
else low = mid+1;
}
dp[low] = p[i];
if(low>len) len++;                            //当low>len表示之前没找到插入位置,必然len++了
}
if(len==1)
printf("Case %d:/nMy king, at most 1 road can be built./n/n",++cas);
else
printf("Case %d:/nMy king, at most %d roads can be built./n/n",++cas,len);
}
}

HDU 3351
#include <cstdio>
#include <algorithm>
#include <memory.h>
#define maxn 2000+1
using namespace std;
char str[maxn];
int main(){
int cas=0;
int ans,sum;
while(scanf("%s",str)!=EOF){
if(str[0]=='-') return 0;
printf("%d. ",++cas);
sum=ans=0;
for(int i=0;str[i];i++){
if(str[i]=='{'){
sum++;
}
else sum--;
if(sum<0){
ans++;
sum=1;
}
}
ans+=sum/2;
printf("%d/n",ans);
}
return 0;
}

1. 可宫非还曾以滚球的形象上过封面啊，这也应该算进去，那让我看看啊……宫非和郝好一起上了封面5次，封以杭和郝好一共上过封面4次，算上以小丰的形象，大家认为呢

2. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

3. #include <cstdio>

int main() {