Editorial for Beads
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#include<functional> #include<algorithm> #include<iostream> #include<cstdio> #include<vector> using namespace std; const int N = 100000, INF = 1e9 + 7; int a[N], lis[N], lds[N], n; void calcLIS(int a[], int n, int res[]) { vector<int> last (n, INF); for(int i = 0; i < n; ++i) { res[i] = lower_bound(last.begin(), last.end(), a[i]) - last.begin(); last[res[i]] = min(last[res[i]], a[i]); } } int main() { ios::sync_with_stdio(false); cin >> n; for(int i = 0; i < n; ++i) cin >> a[i]; reverse(a, a + n); calcLIS(a, n, lis); transform(a, a + n, a, negate<int>()); calcLIS(a, n, lds); int res = 0; for(int i = 0; i < n; ++i) res = max(res, lis[i] + lds[i] + 1); cout << res << endl; return 0; }
Code mẫu của skyvn97
#include<cstdio> #define MAX 100100 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1) int a[MAX]; int ci[MAX]; int cd[MAX]; int fi[MAX]; int fd[MAX]; int n; void maximize(int &x,const int &y) { if (x<y) x=y; } void init(void) { scanf("%d",&n); FORD(i,n,1) scanf("%d",&a[i]); } void LIS(void) { int sz=1; fi[1]=1; ci[1]=1; FOR(i,2,n) { if (a[i]<=a[ci[1]]) { fi[i]=1; ci[1]=i; continue; } if (a[i]>a[ci[sz]]) { sz++; fi[i]=sz; ci[sz]=i; continue; } int l=1; int r=sz; int m; while (true) { if (l==r) { m=r; break; } if (r-l==1) { if (a[i]>a[ci[r]]) m=r; else m=l; break; } m=(l+r)/2; if (a[i]>a[ci[m]]) l=m; else r=m-1; } fi[i]=m+1; if (a[ci[m+1]]>a[i]) ci[m+1]=i; } } void LDS(void) { int sz=1; fd[1]=1; cd[1]=1; FOR(i,2,n) { if (a[i]>=a[cd[1]]) { fd[i]=1; cd[1]=i; continue; } if (a[i]<a[cd[sz]]) { sz++; fd[i]=sz; cd[sz]=i; continue; } int l=1; int r=sz; int m; while (true) { if (l==r) { m=r; break; } if (r-l==1) { if (a[i]<a[cd[r]]) m=r; else m=l; break; } m=(l+r)/2; if (a[i]<a[cd[m]]) l=m; else r=m-1; } fd[i]=m+1; if (a[cd[m+1]]<a[i]) cd[m+1]=i; } } void answer(void) { int res=0; FOR(i,1,n) maximize(res,fi[i]+fd[i]-1); printf("%d",res); } int main(void) { //freopen("BEADS.INP","r",stdin); //freopen("BEADS.OUT","w",stdout); init(); LIS(); LDS(); answer(); return 0; }
Comments