[luoguP1970] 花匠（DP）

传送门

n² 过不了惨啊

70分做法

f[i][0] 表示第 i 个作为高的，的最优解

f[i][0] 表示第 i 个作为低的，的最优解

（且第 i 个一定选）

那么

f[i+1][1]=max(f[j][0])+1,i>=j>=1,h[j]>h[i+1],

f[i+1][0]=max(f[j][1])+1,i>=j>=1,h[j]<h[i+1],

——代码

 #include <cstdio>

 #include <algorithm>

 const int MAXN = , INF = ~( << );

 int n, ans, max;

 int a[MAXN], f[MAXN][];

 inline int Max(int x, int y)

 {

     return x > y ? x : y;

 }

 int main()

 {

     //freopen("flower.in", "r", stdin);

     //freopen("flower.out", "w", stdout);

     int i, j;

     scanf("%d", &n);

     for(i = ; i <= n; i++) scanf("%d", &a[i]);

     for(i = ; i <= n; i++)

     {

         max = ;

         for(j = ; j < i; j++)

             if(a[j] < a[i] && f[j][] > max)

                 max = f[j][];

         f[i][] = max + ;

         ans = Max(ans, f[i][]);

         max = ;

         for(j = ; j < i; j++)

             if(a[j] > a[i] && f[j][] > max)

                 max = f[j][];

         f[i][] = max + ;

         ans = Max(ans, f[i][]);

     }

     printf("%d\n", ans);

     return ;

 }

100分

我们发现上面的方程可以用线段树优化，可以建一颗权值线段树

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define root 1, 1, size

 #define ls now << 1, l, mid

 #define rs now << 1 | 1, mid + 1, r

 const int MAXN = ;

 int n, size;

 int a[MAXN], b[MAXN], f[MAXN][], max[MAXN << ][];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int Max(int x, int y)

 {

     return x > y ? x : y;

 }

 inline void pushup(int now)

 {

     max[now][] = Max(max[now][], max[now << ][]);

     max[now][] = Max(max[now][], max[now <<  | ][]);

     max[now][] = Max(max[now][], max[now << ][]);

     max[now][] = Max(max[now][], max[now <<  | ][]);

 }

 inline int query(int x, int y, int k, int now, int l, int r)

 {

     if(x <= l && r <= y) return max[now][k];

     int mid = (l + r) >> ;

     if(l > y || r < x) return ;

     return Max(query(x, y, k, ls), query(x, y, k, rs));

 }

 inline void update(int x, int a, int b, int now, int l, int r)

 {

     if(l == r)

     {

         max[now][] = Max(max[now][], a);

         max[now][] = Max(max[now][], b);

         return;

     }

     int mid = (l + r) >> ;

     if(x <= mid) update(x, a, b, ls);

     else update(x, a, b, rs);

     pushup(now);

 }

 int main()

 {

     int i;

     n = read();

     for(i = ; i <= n; i++) a[i] = b[i] = read();

     std::sort(b + , b + n + );

     size = std::unique(b + , b + n + ) - (b + );

     for(i = ; i <= n; i++) a[i] = std::lower_bound(b + , b + size + , a[i]) - b;

     for(i = ; i <= n; i++)

     {

         f[i][] = query(, a[i] - , , root) + ;

         f[i][] = query(a[i] + , size, , root) + ;

         update(a[i], f[i][], f[i][], root);

     }

     printf("%d\n", Max(f[n][], f[n][]));

     return ;

 }

100分

用个p线段树，树状数组维护前后缀就好。

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define root 1, 1, size

 #define ls now << 1, l, mid

 #define rs now << 1 | 1, mid + 1, r

 const int MAXN = ;

 int n, ans;

 int c0[MAXN], c1[MAXN];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline int max(int x, int y)

 {

     return x > y ? x : y;

 }

 inline int query1(int x)

 {

     int ret = ;

     for(; x <= MAXN; x += x & -x) ret = max(ret, c1[x]);

     return ret;

 }

 inline int query0(int x)

 {

     int ret = ;

     for(; x; x -= x & -x) ret = max(ret, c0[x]);

     return ret;

 }

 inline void update0(int x, int d)

 {

     for(; x <= MAXN; x += x & -x) c0[x] = max(c0[x], d);

 }

 inline void update1(int x, int d)

 {

     for(; x; x -= x & -x) c1[x] = max(c1[x], d);

 }

 int main()

 {

     int i, x, y, z;

     n = read();

     for(i = ; i <= n; i++)

     {

         z = read() + ;

         x = query1(z + ) + ;

         y = query0(z - ) + ;

         update0(z, x);

         update1(z, y);

         ans = max(ans, max(x, y));

     }

     printf("%d\n", ans);

     return ;

 }

100分

f[i][0] 表示第 i 个作为高的，的最优解

f[i][0] 表示第 i 个作为低的，的最优解

（然而第 i 个不一定选）

那么

h[i]>h[i−1]时，

f[i][0]=max{f[i−1][0],f[i−1][1]+1},f[i][1]=f[i−1][1];

h[i]==h[i−1]时，

f[i][0]=f[i−1][0],f[i][1]=f[i−1][1];

h[i]<h[i−1]时，

f[i][0]=f[i−1][0],f[i][1]=max{f[i−1][1],f[i−1][0]+1}.

答案ans=max{f[n][0],f[n][1]};

边界为f[1][0]=f[1][1]=1

——代码

 #include <cstdio>

 #include <algorithm>

 const int MAXN = , INF = ~( << );

 int n, ans;

 int a[MAXN], f[MAXN][];

 inline int max(int x, int y)

 {

     return x > y ? x : y;

 }

 int main()

 {

     //freopen("flower.in", "r", stdin);

     //freopen("flower.out", "w", stdout);

     int i, j;

     scanf("%d", &n);

     for(i = ; i <= n; i++) scanf("%d", &a[i]);

     f[][] = f[][] = ;

     for(i = ; i <= n; i++)

     {

         if(a[i] > a[i - ])

         {

             f[i][] = max(f[i - ][], f[i - ][] + );

             f[i][] = f[i - ][];

         }

         else if(a[i] == a[i - ])

         {

             f[i][] = f[i - ][];

             f[i][] = f[i - ][];

         }

         else

         {

             f[i][] = f[i - ][];

             f[i][] = max(f[i - ][], f[i - ][] + );

         }

     }

     printf("%d\n", max(f[n][], f[n][]));

     return ;

 }

巴特西

[luoguP1970] 花匠（DP）

最新文章

热门文章