4月24日

poj1065

题意:给定木棒的长度和重量，将n跟木棒进行加工，若后一根木棒的长度和重量都大于前一跟，则可以继续进行加工，否则需要停下来重新对刀，开始第一次要停下来一次，问最少停下来几次

分析:一个非常好的dp题目，需要好好总结一下，我们可以将木棒按照长度和重量任意一个进行升序排序，对另外一个求最长下降子序列，这样我们就知道总共最少停刀了多少次了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <set>
 8 #include <map>
 9 #include <bitset>
10 #include <cmath>
11 #include <queue>
12 #include <stack>
13 using namespace std;
14 const int maxn=5050;
15 typedef struct p
16 {
17     int l,w;
18 }p; 
19 p s[maxn];
20 int dp[maxn];
21 int vis[maxn];
22 bool cmp(p a,p b)
23 {
24     if(a.l==b.l) return a.w<b.w;
25     else return a.l<b.l;
26 }
27 int n,t;
28 int main()
29 {
30     cin>>t;
31     while(t--)
32     {
33         cin>>n;
34         for(int i=0;i<n;i++)
35             scanf("%d%d",&s[i].l,&s[i].w);
36         sort(s,s+n,cmp);
37         memset(dp,0,sizeof(dp));
38         int res=0;
39         for(int i=0;i<n;i++)
40         {
41             dp[i]=1;
42             for(int j=0;j<i;j++){
43                 if(s[j].w>s[i].w)
44                     dp[i]=max(dp[i],dp[j]+1);
45             }
46             res=max(res,dp[i]);
47         }
48         cout<<res<<endl;
49     }
50     return 0;
51 }

View Code

poj1631

题意:给定n个路由的连接方式，求其中最多有多少条不相交

分析:最长上升子序列问题，要不相交，我们必须认为其断点再不断上升，但是看看数据范围，要用nlogn的算法,dp[i]表示长度为i＋1的数列最后一位的最小值，最后一位越小，越可能构成长的上升子序列,然后若dp[0]或者dp[i-1]<a[j],则dp[i]=min(dp[i],a[j])，然后因为dp数组里面的元素都是升序，所以可以二分进行优化，注意stl里面的lower_bound的用法，详见《挑战程序设计》64到66页

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <vector>
 6 #include <algorithm>
 7 #include <set>
 8 #include <map>
 9 #include <bitset>
10 #include <cmath>
11 #include <queue>
12 #include <stack>
13 #define INF 0x3ffff
14 using namespace std;
15 const int maxn=40050;
16 int a[maxn];
17 int dp[maxn];
18 int n,t;
19 int main()
20 {
21     cin>>t;
22     while(t--)
23     {
24         cin>>n;
25         for(int i=0;i<n;i++)
26             scanf("%d",&a[i]);
27         fill(dp,dp+n,INF);
28         for(int i=0;i<n;i++){
29             *lower_bound(dp,dp+n,a[i])=a[i];
30         }
31         cout<<lower_bound(dp,dp+n,INF)-dp<<endl;
32     }
33     return 0;
34 }

View Code