首页 > ACM题库 > HDU-杭电 > HDU 1275 两车追及或相遇问题-动态规划-[解题报告] C++
2013
12-04

HDU 1275 两车追及或相遇问题-动态规划-[解题报告] C++

两车追及或相遇问题

问题描述 :

外号叫“猪头三”的小学生在数学课上,经常遇到两车相遇或追及的方程题,经过长时间的练习,他发现了许多规律,然而他不懂计算机,他想请你帮忙编写一个计算机程序,解决他的问题。
题目的描述是这样的:甲、乙两地相距L公里,A车的速度为VA公里/小时,B车的速度为VB公里/小时,A车和B车开始时分别在甲、乙两地,现在两车同时从甲、乙两地出发,并且开始计时,两车到达甲、乙两地后返回继续行驶,这样会有许多次追及或相遇的时候,我们假定称追及或相遇的时候为“重合”,请输出“重合”时的时间以及离甲、乙两地较近地的距离。

输入:

本题有多个测试数据组,第一行为测试数据组数N,接着是N行数据,每行的数据按顺序分别为实数类型的距离、A车的速度、B车的速度以及整数类型的第几次“重合”的序号数(<=1000)。

输出:

Time=xxxx.xxx Dist=xx.xxx输出的精度为精确到小数点后三位。

样例输入:

2
120.7 90.0 90.0 10
100.5 80.7 69.3 1

样例输出:

Time=12.741 Dist=60.350
Time=0.670 Dist=46.431

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1257

题目链接:

 

1257

解题思路:

    一开始一直纠结在求最小下降的次数(从大减少到最小的的为一次)。 想了很久才恍然大悟,这题可以转换成求最长非降子序列。贪心思想。

http://acm.hdu.edu.cn/showproblem.php?pid=1257#include <iostream>
 #include <cstdio>
 #include <cmath>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 const int maxn=150000;
 int  max_len[maxn];
 int  f[maxn];
 
 int main()
 {
     int  n, flag;
     while(cin >> n)
     {
         for(int i=1; i<=n; i++)
             cin >> f[i];
         int  Max=-1;
         for(int i=1; i<=n; i++)
         {
             max_len[i]=1;
             for(int j=1; j<i; j++)
             {
                 if( f[j]<f[i] && max_len[j]+1>max_len[i])
                 {
                     max_len[i]=max_len[j]+1;
                 }
             }
             if(Max<max_len[i])
             {
                 Max=max_len[i];
             }
         }
         cout << Max <<endl;
     }
     return 0;
 }

 

1677

题目大意:给你n个宽为w,高为h的洋娃娃,小的洋娃娃能装到大的洋娃娃里面。问你尽可能装完后剩下的洋娃娃数。

解题思路:

      这题和上一题思想类似,先排个序,注意排序的时候w从大到小排,当w相等时h从小到大排,这么排的原因是w或者h相同的不能被装下(后面的dp会让你清楚为什么这么排)。接下来如果和上题一样用直接用贪心做的话,TLE,囧。

     这题要换种做法,用dp。将排序后的h存入dp[0~n-1]中,再从0开始对这个序列进行遍历。定义一个max_len最长递增序列长度。如果第i个h大于前面存的,max_len加1,并存入dp[max_len]的最后一个。如果小于第j个(j属于(0~max_len-1)),则将第dp[i]替换第dp[j]。以此类推,动态的更新存储求得的max_len就是最大的了。

#include <iostream>
 #include <cstdio>
 #include <cmath>
 #include <algorithm>
 #include <cstring>
 using namespace std;
 
 const int maxn=20005;
 int  dp[maxn];
 
 struct node
 {
     int w, h;
 }f[maxn];
 
 bool cmp(node A, node B)
 {
     if(A.w!=B.w)
         return A.w>B.w;
     else
         return A.h<B.h;
 }
 
 int LIS(int n)
 {
     int max_len=0, i, j;
     for(i=0; i<n; i++)
     {
         for(j=0; j<max_len; j++)
           if(dp[i]<dp[j]) break;
         if(j==max_len) max_len++;
         dp[j]=dp[i];
     }
     return max_len;
 }
 
 int main()
 {
     int  T, n;
     cin >> T;
     while(T--)
     {
         cin >> n;
         for(int i=0; i<n; i++)
             scanf("%d%d",&f[i].w,&f[i].h);
         sort(f,f+n,cmp);
         memset(dp,0,sizeof(dp));
         for(int i=0; i<n; i++)
             dp[i]=f[i].h;
         cout << LIS(n) <<endl;
     }
     return 0;
 }

 


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])