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.

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

Please read the guidelines before commenting.


There are no comments at the moment.