【HDU 1275 && HDU 1677】两题类似，经典 DP。

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

题目链接：

1257

解题思路：

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

 1 http://acm.hdu.edu.cn/showproblem.php?pid=1257#include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 const int maxn=150000;
 9 int  max_len[maxn];
10 int  f[maxn];
11 
12 int main()
13 {
14     int  n, flag;
15     while(cin >> n)
16     {
17         for(int i=1; i<=n; i++)
18             cin >> f[i];
19         int  Max=-1;
20         for(int i=1; i<=n; i++)
21         {
22             max_len[i]=1;
23             for(int j=1; j<i; j++)
24             {
25                 if( f[j]<f[i] && max_len[j]+1>max_len[i])
26                 {
27                     max_len[i]=max_len[j]+1;
28                 }
29             }
30             if(Max<max_len[i])
31             {
32                 Max=max_len[i];
33             }
34         }
35         cout << Max <<endl;
36     }
37     return 0;
38 }

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就是最大的了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 const int maxn=20005;
 9 int  dp[maxn];
10 
11 struct node
12 {
13     int w, h;
14 }f[maxn];
15 
16 bool cmp(node A, node B)
17 {
18     if(A.w!=B.w)
19         return A.w>B.w;
20     else
21         return A.h<B.h;
22 }
23 
24 int LIS(int n)
25 {
26     int max_len=0, i, j;
27     for(i=0; i<n; i++)
28     {
29         for(j=0; j<max_len; j++)
30           if(dp[i]<dp[j]) break;
31         if(j==max_len) max_len++;
32         dp[j]=dp[i];
33     }
34     return max_len;
35 }
36 
37 int main()
38 {
39     int  T, n;
40     cin >> T;
41     while(T--)
42     {
43         cin >> n;
44         for(int i=0; i<n; i++)
45             scanf("%d%d",&f[i].w,&f[i].h);
46         sort(f,f+n,cmp);
47         memset(dp,0,sizeof(dp));
48         for(int i=0; i<n; i++)
49             dp[i]=f[i].h;
50         cout << LIS(n) <<endl;
51     }
52     return 0;
53 }

【HDU 1275 && HDU 1677】 两题类似，经典 DP。

【HDU 1275 && HDU 1677】两题类似，经典 DP。