Editorial for VO 12 Bài 4 - Dãy con không giảm dài nhất
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 flashmt
#include <iostream> #include <algorithm> #define oo 2000000001 using namespace std; int main() { int n,d,a[1010],last[1010]; cin >> n >> d; for (int i=0;i<=1000;i++) last[i]=(i?oo:-oo); for (int i=1;i<=n;i++) { cin >> a[i]; for (int j=i;j;j--) if (a[i]-d>last[j-1]) last[j]=min(last[j],a[i]-d); else if (a[i]+d>=last[j-1]) last[j]=min(last[j],last[j-1]); } for (int ans=n;ans;ans--) if (last[ans]!=oo) { cout << ans << endl; return 0; } }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int N = 1010; using namespace std; int bit[N * N], c[N * N]; int a[N][2]; int n, D, v; vector<iii> b; void Upd(int i, int val) {for(; i <= v; i += i & -i) bit[i] = max(bit[i], val);} int Get(int i) {int s = 0; for(; i; i -= i & -i) s = max(s, bit[i]); return s;} int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> D; for(int i = 1; i <= n; i++) { cin >> v; a[i][1] = v - D; a[i][2] = v + D; b.push_back(iii(a[i][1], ii(i, 1))); b.push_back(iii(a[i][2], ii(i, 2))); } sort(b.begin(), b.end()); v = 0; for(int i = 0; i < b.size(); i++) { if (i == 0 || b[i].X != b[i - 1].X) v++; a[b[i].Y.X][b[i].Y.Y] = v; } int m = 0; for(int i = 1; i <= n; i++) for(int j = a[i][2]; j >= a[i][1]; j--) c[++m] = j; int res = 0, F; for(int i = 1; i <= m; i++) { F = Get(c[i]) + 1; Upd(c[i], F); res = max(res, F); } cout << res; return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int oo = 2000111000; int f[1011][1011], a[1011]; int main() { int n, d; scanf("%d%d", &n, &d); FOR(i,1,n) scanf("%d", &a[i]); int res = 0; FOR(i,0,n) FOR(k,1,n) { if (k > i) f[i][k] = oo; else if (k == 1) { f[i][k] = min(f[i-1][k], a[i]-d); } else { f[i][k] = f[i-1][k]; if (a[i]+d >= f[i-1][k-1]) f[i][k] = min(f[i][k], max(f[i-1][k-1], a[i]-d)); } if (f[i][k] < oo) res = max(res, k); } printf("%d\n", res); return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define ep 0.00001 #define maxn 1011 #define oo 2000000001 #define modunlo 111539786 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int n,d,f[maxn][maxn],a; int main(){ // freopen("input.in","r",stdin); // freopen("output.out","w",stdout); scanf("%d %d",&n,&d); for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) f[i][j] = oo; for(int i = 0; i <= n; i++) f[i][0] = -oo; for(int i = 1; i <= n; i++){ scanf("%d",&a); for(int j = 1; j <= i; j++){ f[i][j] = f[i-1][j]; if(a + d >= f[i-1][j-1]) f[i][j] = min(f[i][j], max(f[i-1][j-1],a - d)); } } for(int i = n; i >= 1; i--) if(f[n][i] < oo){ printf("%d\n",i); return 0; } }
Comments