NYOJ心急的C小加—

NYOJ心急的C小加——贪心

这个题会联想到拦截导弹的题目http://codevs.cn/problem/1044/

首先用动态规划，利用Dilworth定理解题，然而超时了(╥╯^╰╥)

关于Dilworth定理，我的理解：

　　389 207 155 300 299 170 158 65

　　最长不上升子序列（389 300 299 170 158 65）“最多能拦截6个导弹”；

　　最长上升子序列，即最少的链划分数为2，“要拦截所有导弹需要2套系统”。

 1 //2016.2.24
 2 //心急的C小加
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 using namespace std;
 8 
 9 const int maxn=5000+10;
10 int dp[maxn];
11 int n,cnt;    
12 
13 struct  Wood{
14     int length;
15     int weight;
16     Wood(int l=0,int w=0):length(l),weight(w){}
17 }wood[maxn];
18 
19 //按质量大小排序，质量相同的按长度排序
20 bool cmp(const Wood &a,const Wood &b){     
21     if(a.weight==b.weight){
22         return a.length<=b.length;
23     }else{
24         return a.weight<=b.weight;
25     }
26 }
27 
28 //Dilworth定理，求最长非上升子序列---------超时 
29 void solve(){
30     cnt=0;
31     for(int i=0;i<n;i++){
32         dp[i]=1;
33         for(int j=0;j<i;j++){
34             if(wood[j].length>wood[i].length){
35                 dp[i]=max(dp[i],dp[j]+1);
36             }
37         }
38         cnt=max(cnt,dp[i]);
39     }
40     cout<<cnt<<endl;
41 }
42 
43 int main(){
44     int t;
45     cin>>t;
46     while(t--){
47         cin>>n;
48         for(int i=0;i<n;i++){
49             cin>>wood[i].length>>wood[i].weight;
50         }
51         sort(wood,wood+n,cmp);    
52         solve();
53     }
54     return 0;
55 }

下面是AC代码：

 1 //2014.2.25
 2 //心急的C小加
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 using namespace std;
 8 
 9 const int maxn=5000+10;
10 int n;    
11 
12 struct  Wood{
13     int length;
14     int weight;
15     int isVisit;                             //增加一个标记位 
16     Wood(int l=0,int w=0,int v=0):length(l),weight(w),isVisit(v){}
17 }wood[maxn];
18 
19 //按质量大小排序，质量相同的按长度排序
20 bool cmp(const Wood &a,const Wood &b){     
21     if(a.weight==b.weight){
22         return a.length<=b.length;
23     }else{
24         return a.weight<=b.weight;
25     }
26 }
27 
28 void solve(){
29     int tmp,cnt=0;
30     for(int i=0;i<n;i++){
31         if(wood[i].isVisit==0){         
32             cnt++;             
33             tmp=wood[i].length;
34             for(int j=i+1;j<n;j++){
35                 if(wood[j].isVisit==0&&wood[j].length>=tmp){
36                     tmp=wood[j].length;
37                     wood[j].isVisit=1;        //如果满足增序就标志为1 
38                 }
39             }
40         }
41     }
42     cout<<cnt<<endl;
43 }
44 
45 int main(){
46     int t;
47     cin>>t;
48     while(t--){
49         cin>>n;
50         for(int i=0;i<n;i++){
51             cin>>wood[i].length>>wood[i].weight;
52             wood[i].isVisit=0;　　　　　　　　　　//初始化很容易忘记！
53         }
54         sort(wood,wood+n,cmp);    　　　　　　　
55         solve();
56     }
57     return 0;
58 }