本來覺得這不是經典的貪心嗎。。果斷水一次,wa了,看了看discuss,發現貌似不好水,土土的DP了一下,復雜度很高了,又T了。。。然后想想單調隊列,二分什么的。。。不好往上加,直接搞了標記數組flag,暴力從大到小,遍歷尋找,然后就過了。。。這算是優化嗎,瞎搞。。。
1 #include <cstring> 2 #include <cstdio> 3 #include < string > 4 #include <iostream> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 struct node 9 { 10 int x,y; 11 }p[ 100001 ]; 12 int dp[ 100001 ]; 13 int flag[ 100001 ]; 14 int cmp(node a,node b) 15 { 16 if (a.x == b.x) 17 return a.y < b.y; 18 else 19 return a.x < b.x; 20 } 21 int main() 22 { 23 int n,i,j,ans,maxz,top; 24 scanf( " %d " ,& n); 25 for (i = 0 ;i < n;i ++ ) 26 { 27 scanf( " %d%d " ,&p[i].x,& p[i].y); 28 } 29 memset(flag,- 1 , sizeof (flag)); 30 sort(p,p+ n,cmp); 31 ans = 1 ; 32 dp[ 0 ] = 1 ; 33 flag[ 1 ] = p[ 0 ].y; 34 top = 1 ; 35 for (i = 1 ;i < n;i ++ ) 36 { 37 maxz = 0 ; 38 for (j = top;j >= 1 ;j -- ) 39 { 40 if (p[i].x > flag[j]) 41 { 42 maxz = j; 43 break ; 44 } 45 } 46 dp[i] = maxz + 1 ; 47 if (flag[maxz+ 1 ] == - 1 ) 48 { 49 flag[maxz+ 1 ] = p[i].y; 50 top ++ ; 51 } 52 else 53 flag[maxz+ 1 ] = min(flag[maxz+ 1 ],p[i].y); 54 } 55 printf( " %d\n " ,top); 56 }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
