首页 > ACM题库 > HDU-杭电 > HDU 3392-Pie-动态规划-[解题报告]HOJ
2014
03-23

HDU 3392-Pie-动态规划-[解题报告]HOJ

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

 

这是我做的第一个用2个dp数组完成的题目

因为CapsLock键有开关2种状态,所以需要2个数组来记录转移的状态

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

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

注意:这个状态下,dp[0]要初始化为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

 

题目意思是判断至少加多少个字母可以让这个字符串变成回文串

根据回文的性质很容易想到正反串对比,N-LCS的值就是答案了

下面就是LCS的问题了

这里字符串长度为5000,如果用一般LCS的方法开到dp[5000][5000]明显MLE

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

 

题目意思要在2边建立很多路,这些路不能交叉,看最多能建多少条路

题目明显是LIS的变形,只不过数据有 500000,要用到N*LOG(N)的算法来做

否则TLE MLE各种LE

解释下N*LOG(N)的算法。

一般做法每次都要从i-1向前找,找到比i小并且长度最大的那个值

这样的开销,绝对是不能做500000这样的数据的。

1 4 3 5 4

仔细看这组数据,第3个数(3)和第2个数(4),长度都为2,但是3比4小,每次由第i个向前比的时候,4失去了意义,

比如第5个数向前推,134 可以为3,144却非法了,也就是说,我们只要保存相同长度下的最后一个数字为最小的那个最小数字就足够了

代码如下

#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;
}

 

参考:http://blog.csdn.net/naive_nico/article/details/6289448


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

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }