程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [NOIP2013] 花匠,noip2013花匠

[NOIP2013] 花匠,noip2013花匠

編輯:C++入門知識

[NOIP2013] 花匠,noip2013花匠


初看這道題想到O(n2) 的暴力dp

用f[i][0]表示取第i個點為最低點時的答案, f[i][1]為最高點,且f[i][0] = max( f[j][1] ) +1

這樣每次都要查詢前面區間滿足 h[i]>h[j] 的最大值, 可以考慮 線段樹區間查詢 或者 BIT 或者BST , 時間降至O(nlogn)

但是BIT時要注意查詢h[i]<h[j] 條件時涉及到 j ~ maxheight 的最值查詢, 可以把maxheight -h[i] +2 (BIT下標不為0) 存入樹狀數組

RE 代碼:BIT 誤取最大下標為n!! 實際上應該在讀入時求出maxheight!!

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; #define lowbit(x) x&-x #define smax(x,tmp) x=max(x,tmp) const int maxn=100005; const int INF=0x3f3f3f3f; int high[maxn],low[maxn];//!! LAST RE!!! BIT must be bigger!! maxheight!!! int f[maxn][2];//0: low point ; 1: high point int a[maxn]; int n; int maxheight=-INF; inline void add_low(int x,int val) { for(int i=x;i<=maxheight+1;i+=lowbit(i)) smax(low[i],val);//also easy to consider as n!! } inline void add_high(int x,int val) { for(int i=x;i<=maxheight+1;i+=lowbit(i)) smax(high[i],val); } inline int query_low(int x) { int ret=0; for(int i=x;i;i-=lowbit(i)) smax(ret,low[i]); return ret; } inline int query_high(int x) { int ret=0; for(int i=x;i;i-=lowbit(i)) smax(ret,high[i]); return ret; } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),smax(maxheight,a[i]); int ans=1; f[1][0]=f[1][1]=1; add_low(a[1]+1,f[1][0]);add_high(maxheight-a[1]+2,f[1][1]);//add reversely, to query the max !! for(int i=2;i<=n;i++) { f[i][0]=query_high(maxheight-a[i]+1)+1; f[i][1]=query_low(a[i])+1; add_low(a[i]+1,f[i][0]);//can't either!! add_high(maxheight-a[i]+2,f[i][1]);// mustn't use the 0 point !! smax(ans,max(f[i][0],f[i][1])); } printf("%d",ans); return 0; } View Code

AC代碼:(BIT)

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; #define lowbit(x) x&-x #define smax(x,tmp) x=max(x,tmp) const int maxn=100005; const int maxh=1000005; const int INF=0x3f3f3f3f; int high[maxh],low[maxh];//for BIT int f[maxn][2];//0: low point ; 1: high point int a[maxn]; int n; int maxheight=-INF; inline void add_low(int x,int val) { for(int i=x;i<=maxheight+1;i+=lowbit(i)) smax(low[i],val); } inline void add_high(int x,int val) { for(int i=x;i<=maxheight+1;i+=lowbit(i)) smax(high[i],val); } inline int query_low(int x) { int ret=0; for(int i=x;i;i-=lowbit(i)) smax(ret,low[i]); return ret; } inline int query_high(int x) { int ret=0; for(int i=x;i;i-=lowbit(i)) smax(ret,high[i]); return ret; } int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),smax(maxheight,a[i]); int ans=1; f[1][0]=f[1][1]=1; add_low(a[1]+1,f[1][0]);add_high(maxheight-a[1]+2,f[1][1]);//add reversely, to query the max !! for(int i=2;i<=n;i++) { f[i][0]=query_high(maxheight-a[i]+1)+1; f[i][1]=query_low(a[i])+1; add_low(a[i]+1,f[i][0]);//can't either!! add_high(maxheight-a[i]+2,f[i][1]);// mustn't use the 0 point !! smax(ans,max(f[i][0],f[i][1])); } printf("%d",ans); return 0; } //O(n): f[i][0,1] indicates that don't need to stop at i, but had the previous cases //O(n): find the corners with the tendency View Code

 

現慮另一種 O(n) 的dp

用f[i][0,1] 表示 i 及其以前所有高度的最大值,但是0 表示之前出於下降階段而並非之前的上一個節點為轉折點, 僅僅表示一個趨勢

 

另一種 o(n) 算法

由於一段相同變化趨勢的區段內只能留下一個端點

故只需要統計出所有的”拐點“即可!

WA代碼: 只考慮到相鄰的幾個數,但是缺乏長遠的考慮!!!!應用趨勢來判斷!!

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; #define lowbit(x) x&-x #define smax(x,tmp) x=max(x,tmp) const int maxn=100005; const int INF=0x3f3f3f3f; int n; int a[maxn]; int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); int ans=2; for(int i=2;i^n;i++) { if(a[i-1]>a[i] && a[i]<a[i+1]) ans++;//Last WA!! not only the near one, but long trems if(a[i-1]<a[i] && a[i]>a[i+1]) ans++; } printf("%d",ans); return 0; } View Code

AC代碼:

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> #ifdef WIN32 #define AUTO "%I64d" #else #define AUTO "%lld" #endif using namespace std; #define lowbit(x) x&-x #define smax(x,tmp) x=max(x,tmp) const int maxn=100005; const int INF=0x3f3f3f3f; int n; int a[maxn]; int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); int ans=1;//indicates the first one to start!! int flag=0;//indicates start!! for(int i=1;i^n;i++) { if(a[i]<a[i+1] && (flag==0 || flag==-1)) flag=1,ans++; if(a[i]>a[i+1] && (flag==0 || flag==1)) flag=-1,ans++; } printf("%d",ans); return 0; } View Code

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved