您的位置: 首页  >  IT文章  >  [luoguP1970] 花匠（DP）

[luoguP1970] 花匠（DP）

分类: IT文章 • 2022-06-07 13:57:57

传送门

n2 过不了惨啊

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],

——代码

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 const int MAXN = 100001, INF = ~(1 << 31);
 5 int n, ans, max;
 6 int a[MAXN], f[MAXN][2];
 7 
 8 inline int Max(int x, int y)
 9 {
10     return x > y ? x : y;
11 }
12 
13 int main()
14 {
15     //freopen("flower.in", "r", stdin);
16     //freopen("flower.out", "w", stdout);
17     int i, j;
18     scanf("%d", &n);
19     for(i = 1; i <= n; i++) scanf("%d", &a[i]);
20     for(i = 1; i <= n; i++)
21     {
22         max = 0;
23         for(j = 1; j < i; j++)
24             if(a[j] < a[i] && f[j][1] > max)
25                 max = f[j][1];
26         f[i][0] = max + 1;
27         ans = Max(ans, f[i][0]);
28         max = 0;
29         for(j = 1; j < i; j++)
30             if(a[j] > a[i] && f[j][0] > max)
31                 max = f[j][0];
32         f[i][1] = max + 1;
33         ans = Max(ans, f[i][1]);
34     }
35     printf("%d
", ans);
36     return 0;
37 }
View Code

100分

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

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #define root 1, 1, size
 5 #define ls now << 1, l, mid
 6 #define rs now << 1 | 1, mid + 1, r
 7 
 8 const int MAXN = 100001;
 9 int n, size;
10 int a[MAXN], b[MAXN], f[MAXN][2], max[MAXN << 2][2];
11 
12 inline int read()
13 {
14     int x = 0, f = 1;
15     char ch = getchar();
16     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
17     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
18     return x * f;
19 }
20 
21 inline int Max(int x, int y)
22 {
23     return x > y ? x : y;
24 }
25 
26 inline void pushup(int now)
27 {
28     max[now][0] = Max(max[now][0], max[now << 1][0]);
29     max[now][0] = Max(max[now][0], max[now << 1 | 1][0]);
30     max[now][1] = Max(max[now][1], max[now << 1][1]);
31     max[now][1] = Max(max[now][1], max[now << 1 | 1][1]);
32 }
33 
34 inline int query(int x, int y, int k, int now, int l, int r)
35 {
36     if(x <= l && r <= y) return max[now][k];
37     int mid = (l + r) >> 1;
38     if(l > y || r < x) return 0;
39     return Max(query(x, y, k, ls), query(x, y, k, rs));
40 }
41 
42 inline void update(int x, int a, int b, int now, int l, int r)
43 {
44     if(l == r)
45     {
46         max[now][0] = Max(max[now][0], a);
47         max[now][1] = Max(max[now][1], b);
48         return; 
49     }
50     int mid = (l + r) >> 1;
51     if(x <= mid) update(x, a, b, ls);
52     else update(x, a, b, rs);
53     pushup(now);
54 }
55 
56 int main()
57 {
58     int i;
59     n = read();
60     for(i = 1; i <= n; i++) a[i] = b[i] = read();
61     std::sort(b + 1, b + n + 1);
62     size = std::unique(b + 1, b + n + 1) - (b + 1);
63     for(i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + size + 1, a[i]) - b;
64     for(i = 1; i <= n; i++)
65     {
66         f[i][0] = query(1, a[i] - 1, 1, root) + 1;
67         f[i][1] = query(a[i] + 1, size, 0, root) + 1;
68         update(a[i], f[i][0], f[i][1], root);
69     }
70     printf("%d
", Max(f[n][0], f[n][1]));
71     return 0;
72 }
View Code

100分

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

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #define root 1, 1, size
 5 #define ls now << 1, l, mid
 6 #define rs now << 1 | 1, mid + 1, r
 7 
 8 const int MAXN = 1000002;
 9 int n, ans;
10 int c0[MAXN], c1[MAXN];
11 
12 inline int read()
13 {
14     int x = 0, f = 1;
15     char ch = getchar();
16     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
17     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
18     return x * f;
19 }
20 
21 inline int max(int x, int y)
22 {
23     return x > y ? x : y;
24 }
25 
26 inline int query1(int x)
27 {
28     int ret = 0;
29     for(; x <= MAXN; x += x & -x) ret = max(ret, c1[x]);
30     return ret;
31 }
32 
33 inline int query0(int x)
34 {
35     int ret = 0;
36     for(; x; x -= x & -x) ret = max(ret, c0[x]);
37     return ret;
38 }
39 
40 inline void update0(int x, int d)
41 {
42     for(; x <= MAXN; x += x & -x) c0[x] = max(c0[x], d);
43 }
44 
45 inline void update1(int x, int d)
46 {
47     for(; x; x -= x & -x) c1[x] = max(c1[x], d);
48 }
49 
50 int main()
51 {
52     int i, x, y, z;
53     n = read();
54     for(i = 1; i <= n; i++)
55     {
56         z = read() + 1;
57         x = query1(z + 1) + 1;
58         y = query0(z - 1) + 1;
59         update0(z, x);
60         update1(z, y);
61         ans = max(ans, max(x, y));
62     }
63     printf("%d
", ans);
64     return 0;
65 }
View Code

100分

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

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

（然而第 i 个不一定选）

那么

]时， 

; 

]时， 

; 

]时， 

. 

; 

1

——代码

 1 #include <cstdio>
 2 #include <algorithm>
 3 
 4 const int MAXN = 100001, INF = ~(1 << 31);
 5 int n, ans;
 6 int a[MAXN], f[MAXN][2];
 7 
 8 inline int max(int x, int y)
 9 {
10     return x > y ? x : y;
11 }
12 
13 int main()
14 {
15     //freopen("flower.in", "r", stdin);
16     //freopen("flower.out", "w", stdout);
17     int i, j;
18     scanf("%d", &n);
19     for(i = 1; i <= n; i++) scanf("%d", &a[i]);
20     f[1][0] = f[1][1] = 1;
21     for(i = 2; i <= n; i++)
22     {
23         if(a[i] > a[i - 1])
24         {
25             f[i][0] = max(f[i - 1][0], f[i - 1][1] + 1);
26             f[i][1] = f[i - 1][1];
27         }
28         else if(a[i] == a[i - 1])
29         {
30             f[i][0] = f[i - 1][0];
31             f[i][1] = f[i - 1][1];
32         }
33         else
34         {
35             f[i][0] = f[i - 1][0];
36             f[i][1] = max(f[i - 1][1], f[i - 1][0] + 1);
37         }
38     }
39     printf("%d
", max(f[n][0], f[n][1]));
40     return 0;
41 }
View Code

相关推荐