codeforces

Codeforces Round #841 (Div. 2) and Divide by Zero 2022（A-D）

Codeforces Round #841 (Div. 2) and Divide by Zero 2022（A-D）

题目 链接 限制
A Joey Takes Money standard input/output1 s, 256 MB
B Kill Demodogs standard input/output1 s, 256 MB
C Even Subarrays standard input/output2.5 s, 256 MB
D Valiant’s New Map standard input/output2 s, 256 MB

综述

题目有一点点不友好，对于D，竟然….

但是总的难度还行

补题

A Joey Takes Money

image​

202212311249854.png

202212311249855.png

input

1
2
3
4
5
6
7
8
3
3
2 3 2
2
1 3
3
1000000 1000000 1

output

1
2
3
4
28308
8088
2022000000004044

题目大意

给定一个数组，有下列操作

  • 选择两个数字 i 和 j (1≤i<j≤n)
  • 选择两个整数 x 以及 y，使得x⋅y=ai⋅aj
  • 然后使用x替换ai，使用y替换aj

可以使用任意数目的以上操作，使得所有的数字加起来最大。

思路

根据样例，可以猜想，最后把n-1个元素变为1，然后相加起来是最大的。

（贪心）证明：

假设有两个数字不是1，那么他们的值一定大于1，设两个数字为a, b

然后我：a --> a*b, b --> 1比较变化之前以及变化之后的数字大小：

$$
a+b-(a\times b - 1) = (a-1)(1-b)
$$

很小于1

所以变化之后更大。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;;
#define N 55
typedef long long ll;
ll a[N];
int n;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%lld", a+i);
        ll ans = 1;
        for(int i = 1; i <= n; i++) ans *= a[i];
        ans += n - 1;
        ans *= 2022;
        printf("%lld\n", ans);
    }
    return 0;
}

B Kill Demodogs

202212311249856.png

202212311249858.png

input

1
2
3
4
5
4
2
3
50
1000000000

output

1
2
3
4
14154
44484
171010650
999589541

题目大意

给定一个 $n\times n$ 的矩阵，主角开始在$（1，1）$处，目的地在$(n, n)$处。

在每一个单元格上都有怪兽，在第 i 个单元格上的怪兽数量是 $i\times j$.

主角只能向下或者是向右移动。

问：主角最多杀死多少个怪兽。

在这一道题目中，矩阵显然关于斜对角线具有对称性，所以我们选择右上角的观察

202212311249859.png

先凭借知觉，我们观察到，好像中间的数字比较大，所以我们尽可能沿着中间的路走

所以猜想路线：右-下-右-下….

（贪心）证明：

由于每一个格子上的怪兽数目是 $i\times j$

现在我们假设最优解不是我们设想的路径。

202212311249860.png

现在到达（i+1, j+1）有两种路径。

比较通过蓝色路径以及通过红色路径的大小

蓝色路径：$i(j+1)$

红色路径：$(i+1)j$

作差：$i(j+1) - (i+1)j = i - j$

现在假如 j 大于 i ，那么我们就应该走红色路径。

就这样，对于不是最优解的情况，我们可以使用这一种方法不断变成我们的假设。所以我们的假设就是最优解。

然后计算的话就是

$$
maxv = \sum_{i=1}^{n}i^2 + \sum_{n=1}^{n-1}i(i+1) = \sum_{i=1}^{n}i^2 + \sum_{i=1}^{n-1}i^2+\sum_{i=1}^{n-1}i
$$

由于n最大是$10^9$，所以应该使用公式计算

补充相关的数学公式

202212311249861.png

202212311249862.png

1
2
3
4
5
6
7
8
9
10
tim = int(input())
for T in range(tim):
    n = int(input())
    ans = 0
    ans += n*(n+1)*(2*n+1)//6
    ans += (n-1)*n*(2*n-1)//6
    ans += n*(n-1)//2
    ans = ans*2022%1000000007
    print(ans)

其实除法取模（除法逆元）也很简单

前提：

  1. 确保取模的哪一个数字是质数
  2. 确保可以整除

所以有 $a/b = a*b^{mod-2} %mod$

C Even Subarrays

image.png

image.png

image.png

input

1
2
3
4
5
6
7
8
9
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

output

1
2
3
4
4
11
0
20

思路

这一道题目着实很妙。

首先：因数个数是奇数个的数字是非完全平方数。

但是非完全平方数比较多，我们考虑反方面：完全平方数！

首先，要是真的来枚举这一个区间，是不可行的。

对于一个区间来想，可能不是太清晰，所以可以利用前缀和思想，把区间问题转化为端点问题。

sum[L-1] XOR sum[R] == a[L] OXR .....XOR a[R]

然后我们可以枚举R，当务之急就是找到在R之前有多少个前缀与sum[R]异或之后的值是非完全平方数（枚举一遍非完全平方数）。

我们开一个数组cnt[x]记录在R之前的所有前缀中值为x的个数。

然后就可以O(1)求出个数。

总体时间复杂度为O(n*sqrt(2n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 200200
int a[N];
int sum[N];// a的前缀数组
int cnt[N*2];// 两个小于n的数进行异或，值最大不超过2N
signed main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        scanf("%lld", &n);
        for(int i = 1; i <= n; i ++){
            scanf("%lld", a+i);
        }
        int ans = 0;// 答案的反面
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i-1] ^ a[i];
      
        }
        cnt[0] = 1;
        // 这是因为如果sum[R] == 完全平方数，那么其实选择从1到R就可以，所以cnt[0]应该为1
        for(int i = 1; i <= n; i++){
            for(int x = 0; x * x <= 2*n; x++){
                int t = (x*x) ^ sum[i];
                if(t > 2 * n) continue;//因为x * x <= 2*n,所以可能整出来大于2n的
                ans += cnt[t];
            }
            cnt[sum[i]] ++;
        }
      
        printf("%lld\n", (long long)n * (n+1)/2 - ans);
        for(int i = 0; i <= n; i++) {
            sum[i] = 0;
        }
        for(int i = 0; i <= n * 2; i++){
            cnt[i] = 0;
        }
    }

    return 0;
}

D Valiant’s New Map

image.png

image.png

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17

output

1
2
3
4
2
1
1
3

题目大意

给定一个$n\times m$的矩阵，求一个最大值l，使得在矩阵中存在有 $l\times l$ 的方格中的最小值大于等于 l

思路

首先容易证明具有单调性:

如果可以找到使得在矩阵中存在有 $l\times l$ 的方格中的最小值大于等于 l，那么我就在这片区域中一定能找到 $m\times m$ 的方格中的最小值大于等于 m ($m\le l$)

然后问题就成了这样：给定一个框的大小，求有没有一种框法，使得框柱的数字的最小值是给定值。

如果暴力显然时间不够用，但是最小值又不能合起来表示（以一部分的最小值表示）。

但是这里我们的给定值是一个固定的值，所以我们并没有必要知道某一个区域中的最小值是多少，而是仅仅需要知道这一个区域的最小值是不是小于给定值就可以了。

所以我建立一个二维前缀和，如果大于等于给定值，那么我们假想值为0，否则值为1

然后查询前缀和中的值是不是0就可以判断这一种框法是否可行。

但是

这一道题目恶心在数组必须动态开

为此有两种方法：

  • 动态内存分配（额…）
1
2
int **a = (int **)calloc(n, sizeof(int*));
for(int i = 0; i < n; i++) a[i] = (int *)calloc(m, sizeof(int));

别忘了之后还要free!!

注意：开辟后自动有初始值0

  • 使用vector来实现

resize会分配空间，并且自动初始化为0

也可以resize(大小， 初始值)

shrink_to_fit()可以让已经分配的内存空间缩小到size的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
int n, m;
#define N 1100000
bool ck(int mid, int **a, int ** f)
{
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + (a[i][j] < mid);
            // printf("%d ", f[i][j]);
        }
        // puts("");
    }
    for(int i = mid; i <= n; i++){
        for(int j = mid; j <= m; j++){
            if(f[i][j] - f[i - mid][j] - f[i][j - mid] + f[i-mid][j-mid] == 0) return true;
        }
  
    }
    return false;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        //int *a[m + 1] = (int *[m+1])calloc((n+1)*(m+1), sizeof(int));int** p = (int **)malloc(3*sizeof(int*));//申请指针数组
 
        int** a = (int **)malloc((n+1)*sizeof(int*));
 
        for(int i=0; i<n+1; i++)
        {
            a[i] = (int*)malloc((m+1)*sizeof(int));
        }

    	int** f = (int **)malloc((n+1)*sizeof(int*));
  
        for(int i=0; i<n+1; i++)
        {
            f[i] = (int*)malloc((m+1)*sizeof(int));
        }

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }

        int l = 1, r = min(n, m);
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(ck(mid, a, f)) l = mid;
            else r = mid - 1;
        }  
        printf("%d\n", l);
       for(int i=0; i<n+1; i++)
        {
            free(f[i]);
            free(a[i]);
        } 
        free(a);
        free(f);
    }
    return 0;
}
AcWing算法提高课

简单DP+最长上升子序列

简单DP+最长上升子序列

比较简单的DP

1027. 方格取数

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

2.gif​

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式

第一行为一个整数N，表示 N×N 的方格图。

接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。

行和列编号从 1开始。

一行“0 0 0”表示结束。

输出格式

输出一个整数，表示两条路径上取得的最大的和。

数据范围

N≤10≤10

输入样例：

1
2
3
4
5
6
7
8
9
10
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0

输出样例：

1
67

题解

不可以使用贪心（第一次选择最大的一条路径，然后把已经选择过的清空，再选择）

反例：

1
2
3
0  1  0
2  2  2
1  0  0

这里使用f[x1][y1][x2][y2]来进行描述。

但是发现存在状态冗余，所以取一个为横纵坐标之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define N 15
int a[N][N];
int dp[N * 2][N][N];
int n;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {-1, 0, -1, 0};
int solve()
{
    for(int k = 2;  k <= n * 2; k++)
    {
        for(int i = 1; i < k && i <= n; i++)
        {
            for(int j = 1; j < k && j <= n; j++)
            {
                int maxv = 0;
                for(int p = 0; p < 4; p++)
                {
                    int ni = i + dx[p];
                    int nj = j + dy[p];
                    maxv = max(maxv, dp[k - 1][ni][nj]);
                }
                if(i == j) dp[k][i][j] = maxv + a[i][k - i];
                else dp[k][i][j] = maxv + a[i][k - i] + a[j][k - j];
            }
        }
    }
    return dp[n * 2][n][n];
}
int main()
{
    scanf("%d", &n);
    int x, y, z;
    while(scanf("%d%d%d", &x, &y, &z), x || y || z)
    {
        a[x][y] = z;
    }
    cout << solve() << endl;
    return 0;
}

275. 传纸条

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题
一次素质拓展活动中，班上同学安排坐成一个 m行n列的阵，而小渊和小轩被安排在知阵对角线的两端，因此，他们就无法直接交谈了
幸运的是，他们可以通过传纸条来进行交流
纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。
从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复
班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低注意:小渊和小轩的好心程度没有定义，输入时用0表示)，可以用一个0~100的自然数来表示，数越大表示越好心。
小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。
现在，请你帮助小渊和小轩找到这样的两条路径

输入格式
第一行有2个用空格隔开的整数m和n，表示学生矩阵有m行n列接下来的m行是一个mxn的阵，知阵中第行列的整数表示坐在第行列的学生的好心程度，每行的n个整数之间用空格隔开。
输出格式
输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值.
数据范围
1<=n,m <=50

输入样例：

1
2
3
4
3 3
0 3 9
2 8 5
5 7 0

输出样例：

1
34

题解

这一道题目可以直接使用上面的代码。

使用上面的代码求解出来的路径：

  1. 如果两条路径并没有相交，那么就是这一道题目的结果
  2. 如果方块取数的路径有相交的，那么我可以把相交处往外折叠，这样，折叠之后的结果一定优于或与未折叠的一样。而由于方块取数求的是最优解。所以折叠之后的结果等于未折叠的解
    而折叠之后的解就是这一道题目的解。

我就算考虑可以相交的情况，最优解也不过如此，所以上述方法求出来的就是最优解。

使用上一道题目的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define N 55
int a[N][N];
int dp[N * 2][N][N];
int n, m;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {-1, 0, -1, 0};
int solve()
{
    for(int k = 2;  k <= n + m; k++)
    {
        for(int i = 1; i < k && i <= n; i++)
        {
            for(int j = 1; j < k && j <= n; j++)
            {
                int maxv = 0;
                for(int p = 0; p < 4; p++)
                {
                    int ni = i + dx[p];
                    int nj = j + dy[p];
                    maxv = max(maxv, dp[k - 1][ni][nj]);
                }
                if(i == j) dp[k][i][j] = maxv + a[i][k - i];
                else dp[k][i][j] = maxv + a[i][k - i] + a[j][k - j];
            }
        }
    }
    return dp[n+m][n][n];
}
int main()
{
    scanf("%d%d", &n, &m);
   for(int i = 1; i <= n; i++)
   {
       for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
   }
    cout << solve() << endl;
    return 0;
}

把相交的情况设置为非法，然后进行求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
#define N 55
int a[N][N];
int dp[N * 2][N][N];
int n, m;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {-1, 0, -1, 0};
int solve()
{
    for(int k = 2;  k <= n + m; k++)
    {
        for(int i = 1; i < k && i <= n; i++)
        {
            for(int j = 1; j < k && j <= n; j++)
            {
                int maxv = 0;
                for(int p = 0; p < 4; p++)
                {
                    int ni = i + dx[p];
                    int nj = j + dy[p];
                    maxv = max(maxv, dp[k - 1][ni][nj]);
                }
                if(k == 2 && i == 1 && j == 1 || k == n + m && i == n && j == n) 
                    dp[k][i][j] = maxv;
                else if(i == j) dp[k][i][j] = -0x3f3f3f3f;
                else dp[k][i][j] = maxv + a[i][k - i] + a[j][k - j];
            }
        }
    }
    return dp[n+m][n][n];
}
int main()
{
    scanf("%d%d", &n, &m);
   for(int i = 1; i <= n; i++)
   {
       for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
   }
    cout << solve() << endl;
    return 0;
}

最长上升子序列

image​

AcWing1014. 登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式

输出一个整数，表示最多能浏览的景点数。

数据范围

2≤N≤1000

输入样例：

1
2
8
186 186 150 200 160 130 197 220

输出样例：

1
4

题解

三大条件：

  1. 按照顺序来浏览这些景点（必须是子序列）
  2. 不连续浏览海拔相同的两个景点
  3. 一旦开始下山，就不再向上走了

单独看2不好操作，把2与3结合，得到：路线形状为^的左边严格单调递增，右边严格单调递减的路线。

可以枚举顶点的位置，从1到n

在顶点为某一个位置时，左右的最大值并没有关联，所以可以单独求得最大值然后相加。

如果令顶点在一个位置，求解一次，花费$n^2$

求解多次花费貌似是$n^3$，但是动态规划的过程量也已经求解，所以共需要$n^2$可以求解本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define N 1020
int a[N];
int dp1[N];
int dp2[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    for(int i = 1; i <= n; i++){
        int t = 0;
        for(int j = 1; j < i; j++){
            if(a[j] < a[i]) t = max(dp1[j], t); 
        }
        dp1[i] = 1 + t;
    }
    // BUG 记录：我这里这一个是从左边开始，以f[i]为结尾的最长递减子序列
    // for(int i = 1; i <= n; i++){
    //     int t = 0;
    //     for(int j = 1; j < i; j++){
    //         if(a[j] > a[i]) t = max(t, dp2[j]);
    //     }
    //     dp2[i] = t + 1;
    // }
    for(int i = n; i >= 1; i--){
        int t = 0;
        for(int j = n; j > i; j--){
            if(a[i] > a[j]) t = max(t, dp2[j]);
        }
        dp2[i] = t + 1;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(dp1[i] + dp2[i] - 1, ans);
    }
    printf("%d\n", ans);
    return 0;
}

AcWing1012. 友好城市

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式

第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围

1≤N≤5000
0≤xi≤10000

输入样例：

1
2
3
4
5
6
7
8
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例：

1
4

由于这一道题目给的是精确的数字，我们可以进行模糊化处理：

  1. 每一个城市的具体坐标并不影响是否交叉，所以我仅仅关心他们的相对左右有关新。

我们应该按照顺序进行寻找规律（下面的从小到大）

进行试探。选择了南北两个城市，那么我的其他选择只能是新选择的两个城市在已经选择城市的同一侧。

类似于最长上升子序列。

证明充分必要（容易证明）

这里的对应关系可以使用pair进行描述

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define N 5020
typedef pair<int, int> PII;
PII a[N];
int dp[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].first, &a[i].second);
    }
    sort(a+1, a+1+n);
    for(int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1; j < i; j ++){
            if(a[j].second < a[i].second)
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }   
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

1010. 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

输入样例：

1
389 207 155 300 299 170 158 65

输出样例：

1
2
6
2

upload successful

贪心法也可以使用过反证法：
假设贪心不是最优解，但是最后可以把贪心进行调整，使得等于最优解。故假设错误，贪心是最优解。

调整法的精髓：

在保证答案不发生变化的情况下，从最后一个不一样的地方一步一步调整，由于序列是有限的，所以最终可以得到最优解。

到最后的时候，这种贪心方法恰好是求解最长上升子序列的方法（贪心做法）。

所以等价于求解最长上升子序列。

187. 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式

对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围

1≤n≤50

输入样例：

1
2
3
5
3 5 2 4 1
0

输出样例：

1
2

样例解释

对于给出样例，最少需要两套防御系统。

一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1的导弹。

题解（DFS）

参考上一道题目的贪心策略，但是这里对于每一个点具有两种选择：要么上升，要么下降。所以在某一个地方就必须考虑两个情况，所以采用DFS。

时间复杂度：由于题目中的数字全部不一样，所以每一个系统至少可以干掉两个。所以最坏的是$2^{25} = 33,554,432$.在实际的情况下，ans肯定更小，这时候由于第一句的剪枝，所以时间复杂度是可以过去的。

DFS+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define N 55
int n;
int a[N], up[N], down[N];
int ans = 0;
void dfs(int u, int su, int sd)
{
    if(su + sd >= ans) return;// 剪枝
    if(u > n) {
        ans = min(ans, su+sd);
        return;
    }
    int k;
    int tmp;
    k = 1;
    while(k <= su && up[k] >= a[u]) k++;
    //k可能大于su，但是正好相当于后面加了一个
    tmp = up[k];
    up[k] = a[u];
    if(k > su) dfs(u + 1, su+1, sd);
    else dfs(u + 1, su, sd);
    up[k] = tmp;

    k = 1;
    while(k <= sd && down[k] <= a[u]) k++;
    tmp = down[k];
    down[k] = a[u];
    if(k > sd) dfs(u+1, su, sd+1);
    else dfs(u + 1, su, sd);
    down[k] = tmp;
}
int main()
{
    while(scanf("%d", &n), n){
        for(int i = 1; i <= n; i++) scanf("%d", a+i);
        ans = n;//其实是(n+1)/2级别的
        dfs(1, 0, 0);
        printf("%d\n", ans);
    }
  

    return 0;
}

题解（迭代加深）

对于深度优先，如果答案在很浅的部位，但是整个搜索树过于深，那么就会寄掉。

但是对于广度优先，本来挺好，但是在队列里面存储太多的元素，到时爆。同时，广度优先也不容易存储数据。同时还不容易剪枝

对于迭代加深，就是深度与广度的完美结合！

  1. 有着广搜的搜索浅层的时间复杂度
  2. 不会爆空间
  3. 容易利用系统所给的栈来进行存储
  4. 还可以剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
#define N 55
int n;
int a[N];
int up[N];
int down[N];

bool dfs(int ans, int u, int su, int sd)
{
    if(su + sd > ans) return false;
    if(u > n) return true;
  
    int k, tmp;
    k = 1;
    while(k <= su && up[k] >= a[u]) k++;
    tmp = up[k];
    up[k] = a[u];
    /*
惊天动地大BUG：
如果这样：
if(k > su) if(dfs(ans, u+1, su+1, sd)) return true;
else if(dfs(ans, u+1, su, sd)) return true;
那么下面的else是与第一行的第二个if进行配对！！！
    */
    if(k > su) {if(dfs(ans, u+1, su+1, sd)) return true;}
    else if(dfs(ans, u+1, su, sd)) return true;
    up[k] = tmp;
  
    k = 1;
    while(k <= sd && down[k] <= a[u]) k++;
    tmp = down[k];
    down[k] = a[u];
    if(k > sd) {if(dfs(ans, u+1, su, sd+1)) return true;}
    else if(dfs(ans, u+1, su, sd))return true;
    down[k] = tmp;
    return false;
}

int main()
{
    while(scanf("%d", &n), n)
    {
        for(int i = 1; i <= n; i++){
            scanf("%d", a+i);
        }
        int ans = 1;
        while(1){
            if(dfs(ans, 1, 0, 0)){
                break;
            }
            else{
                ans ++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

272. 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了。

数列 A 和 B 的长度均不超过 3000。

输入格式

第一行包含一个整数 N，表示数列 A，B 的长度。

第二行包含 N 个整数，表示数列 A。

第三行包含 N 个整数，表示数列 B。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

1≤N≤3000,序列中的数字均不超过 $2^{31}-1$。

输入样例：

1
2
3
4
2 2 1 3
2 1 2 3

输出样例：

1
2

题解

是最长上升子序列以及最长公共子序列的完美结合。

状态表示

f[i][j]表示a序列中的前 i 项以及b序列中的前 j 项，并且以b[j]结尾（为了便于求解上升。但是并不需要a[i]结尾，这是因为是公共子序列，所以是相等）的所有公共上升子序列

状态属性

最大值

状态转移（对于f[i][j]）

  1. 当f[i][j]的子序列中并不包含a[i]，那么显然有：f[i][j] = f[i-1][j]
  2. 当f[i][j]的子序列中包含a[i]：
    根据状态表示得知：f[i][j]的子序列中包含b[i].所以这一种情况的条件是a[i] == b[j]
    然后枚举a[i-1][k]，如果可以，那么取最小值。

详细见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i-1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
                for(int k = 1; k < j; k++)
                {
                    if(a[i] > b[k]) f[i][j] = max(f[i][j], f[i][k] + 1);
               }
            }
        }
    }

但是需要进行优化：求最大值的时候并没有必要每一次都扫一遍！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i = 1; i <= n; i++)
    {
	int maxv = 0;
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i-1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
		f[i][j] = max(f[i][j], maxv+1);
		if(b[j] < a[i]) maxv = max(maxv, f[i][j]);
            }
        }
    }

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
#define N 3020
int a[N], b[N], f[N][N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    for(int i = 1; i <= n; i++) scanf("%d", b+i);

    for(int i = 1; i <= n; i++)
    {
	    int maxv = 0;
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i-1][j];
            if(a[i] == b[j])
            {
                f[i][j] = max(f[i][j], 1);
		        f[i][j] = max(f[i][j], maxv+1);
            }
	        if(b[j] < a[i]) maxv = max(maxv, f[i][j]);// 这个应该在if(a[i] == b[j])的外面
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(f[n][i], ans);
    }
    printf("%d", ans);
    return 0;
}

完美撒花

about_me

csdn：

1
https://blog.csdn.net/xjsc01

cnblogs:

1
https://www.cnblogs.com/xjsc01/

知乎

1
https://www.zhihu.com/people/xjsc01