参考文献 y总的提高课和基础课

考虑状态转移的时候

我们要着重考虑”最后一步“，

先考虑到最后一步将进行那些操作，对集合进行划分

然后考虑不进行这最后一步的操作的倒数第二个状态是什么状态

然后考虑进行了这个最后一步的操作之后倒数第二个状态将会对最后一个状态发生怎么样的变化

然后将这个最后一步的操作的贡献和倒数第二个状态相加

然后根据状态表示中的属性对划分出来的集合取Max/Min/数量等

1）数字三角形模型

数字三角形

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int w[N][N], f[N][N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            cin >> w[i][j];

    memset(f, -0x3f, sizeof f);

    f[0][0] = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j ++)
            f[i][j] = max(f[i - 1][j - 1] + w[i][j], f[i - 1][j] + w[i][j]);

    int res = 0;
    for(int i = 1; i <= n; i ++)    res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}

摘花生

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int w[N][N], f[N][N];
int n, m;

int main()
{
    int T;
    cin >> T;
    while(T --){
        cin >> n >> m;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                cin >> w[i][j];

        memset(f, 0, sizeof f);
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

        cout << f[n][m] << endl;
    }
    return 0;
}

最低通行费

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int w[N][N], f[N][N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            cin >> w[i][j];

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++){
            if(i == 1 && j == 1)    f[i][j] = w[i][j];
            else{
                f[i][j] = 1e9;
                if(i > 1)   f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);//i>1说明不在第1行，那样就可以从上面转移过来
                if(j > 1)   f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);//j>1说明不在第1列，那样就可以从左面转移过来
            }
        }

    cout << f[n][n] << endl;

    return 0;
}

方格取数

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 15;

int w[N][N], f[N + N][N][N], n;

int main()
{
    cin >> n;
    int a, b, c;
    while(cin >> a >> b >> c, a || b || c)  w[a][b] = c;

    for(int k = 2; k <= n + n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++){
                int i1 = k - i, j1 = k - j;
                if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= n){
                    int t = w[i][i1];
                    if(i != j)  t += w[j][j1];// 判断2条路经是否重合
                    int &x = f[k][i][j];
                    x = max(x, f[k - 1][i][j] + t);
                    x = max(x, f[k - 1][i - 1][j] + t);
                    x = max(x, f[k - 1][i][j - 1] + t);
                    x = max(x, f[k - 1][i - 1][j - 1] + t);
                }
            }

    cout << f[n + n][n][n] << endl;

    return 0;
}

2）最长上升子序列模型

题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

时间复杂度 O(n ^ 2)

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N], f[N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    cin >> a[i];

    for(int i = 1; i <= n; i ++){
        f[i] = 1;// 自身就是一个子序列时
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i ++)    res = max(res, f[i]);
    cout << res << endl;

    return 0;
}

题目描述

给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。

样例

输入样例：
4 5
acbd
abedc
输出样例：
3

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    scanf("%s%s", a + 1, b + 1);

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j])    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }

    cout << f[n][m] << endl;

    return 0;
}

题目描述

给定两个字符串A和B，现在要将A经过若干操作变为B，可进行的操作有：

1. 删除–将字符串A中的某个字符删除。
2. 插入–在字符串A的某个位置插入某个字符。
3. 替换–将字符串A中的某个字符替换为另一个字符。

现在请你求出，将A变为B至少需要进行多少次操作。

样例

输入样例：
10 
AGTCTGACGC
11 
AGTAAGTAGGC
输出样例：
4

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int f[N][N], n, m;
char a[N], b[N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    for(int i = 1; i <= n; i ++)    f[i][0] = i;
    for(int i = 1; i <= m; i ++)    f[0][i] = i;

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j])    f[i][j] = min(f[i - 1][j - 1], f[i][j]);
            else    f[i][j] = min(f[i - 1][j - 1] + 1, f[i][j]);
        }

    cout << f[n][m] << endl;

    return 0;
}

题目描述

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。

不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。

初始时，怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。

因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。

他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。

请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

样例

输入样例：
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
输出样：
6
6
9

题目中能做的决策是只能进行一次反向的上升子序列的飞行或者正向的下降子序列的飞行

所以子需要做一次序列的上升子序列或者下降子序列就可以了

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 110;

int f[N], n, T, a[N];

int main()
{
    cin >> T;
    while(T -- ){
        cin >> n;
        for(int i = 1; i <= n; i ++)    cin >> a[i];

        int res = 0;
        for(int i = 1; i <= n; i ++){
            f[i] = 1;
            for(int j = 1; j < i; j ++)
                if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        for(int i = 1; i <= n; i ++){
            f[i] = 1;
            for(int j = 1; j < i; j ++)
                if(a[j] > a[i]) f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        cout << res << endl;
    }

    return 0;
}

题目描述

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

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

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

样例

输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1010;

int f[N], a[N], n, g[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    cin >> a[i];

    for(int i = 1; i <= n; i ++){
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    for(int i = n; i >= 1; i --){
        g[i] = 1;
        for(int j = n; j > i; j --)
            if(a[j] < a[i]) g[i] = max(g[i], g[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i ++)    res = max(res, f[i] + g[i] - 1);
    cout << res << endl;

    return 0;
}

题目描述

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

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

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

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

样例

输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef pair < int , int > pii;
#define x first
#define y second

const int N = 5010;

pii a[N];
int n, f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n);

    int res = 0;
    for(int i = 1; i <= n; i ++){
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(a[j].y < a[i].y) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;

    return 0;
}

题目描述

一个数的序列 bibi，当 b1<b2<…<bSb1<b2<…<bS 的时候，我们称这个序列是上升的。

对于给定的一个序列(a1,a2,…,aNa1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiKai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N1≤i1<i2<…<iK≤N。

比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。

这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

样例

输入样例：
7
1 7 3 5 9 4 8
输出样例：
18

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int a[N], f[N], n;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    cin >> a[i];

    int res = 0;
    for(int i = 1; i <= n; i ++){
        f[i] = a[i];
        for(int j = 1; j < i; j ++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
        res = max(res, f[i]);
    }
    cout << res << endl;

    return 0;
}

最长上升子序列 II

题目描述

给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。

样例

输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, f[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)    scanf("%d", &a[i]);

    int len = 1;
    f[len] = a[1];
    for(int i = 2; i <= n; i ++){
        if(a[i] > f[len])   f[++ len] = a[i];
        else{
            int cnt = lower_bound(f + 1, f + len + 1, a[i]) - f;
            f[cnt] = a[i];
        }
    }
    cout << len << endl;

    return 0;
}

题目描述

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

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

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

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

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

样例

输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2

1、贪心做法

对于a[i]中每个数，从前往后扫描，

如果没有一个导弹拦截系统（下降子序列）的最后一个数大于等于当前a[i]就新建一个导弹拦截系统（下降子序列的第一个数）

否则就加入到最后一个数大于等于当前a[i]的导弹拦截系统中（下降子序列的最后一个数）

2、Dilworth定理：

U的链划分使用的最少集合数，等于它的最大反链长度。
U的反链划分使用的最少集合数，等于它的最大链长度。

如果是求下降子序列的最小划分，相当于是求最小反链划分，等于最长不下降子序列的长度。

也就是通过最少的最长不上升子序列去覆盖整个序列，就是求这个序列的最长上升子序列

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, a[N], f[N], g[N];

int main()
{
    while(cin >> a[n])  n ++;

    int res = 0;
    for(int i = 0; i < n; i ++){
        f[i] = 1;
        for(int j = 0; j < i; j ++)
            if(a[j] >= a[i])    f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;

    res = 1;
    g[1] = a[0];
    for(int i = 1; i < n; i ++){
        if(a[i] > g[res])   g[++ res] = a[i];
        else{
            int cnt = lower_bound(g + 1, g + 1 + res, a[i]) - g;
            g[cnt] = a[i];
        }
    }
    cout << res << endl;

    return 0;
}

题目描述

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

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

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

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

样例

输入样例：
5
3 5 2 4 1
0 
输出样例：
2

具体参考y总题解和y总视频课

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 55;

int a[N], n, u[N], d[N], ans;

void dfs(int i, int su, int sd)
{
    if(su + sd >= ans)  return ;
    if(i > n){
        ans = min(ans, su + sd);
        return ;
    }

    int k = 0;
    while(k < su && a[i] <= u[k])   k ++;
    int t = u[k];
    u[k] = a[i];
    if(k < su)  dfs(i + 1, su, sd);
    else    dfs(i + 1, su + 1, sd);
    u[k] = t;

    k = 0;
    while(k < sd && a[i] >= d[k])   k ++;
    t = d[k];
    d[k] = a[i];
    if(k < sd)  dfs(i + 1, su, sd);
    else    dfs(i + 1, su, sd + 1);
    d[k] = t;
}

int main()
{
    while(cin >> n, n){
        for(int i = 1; i <= n; i ++)    scanf("%d", &a[i]);

        ans = n;
        dfs(1, 0, 0);
        cout << ans << endl;        
    }

    return 0;
}

题目描述

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

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

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

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

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

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

样例

输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2

优化请参考y总的题解和y总的视频课

C++ 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 3010;

int a[N], b[N], n, f[N][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]);

    int res = 0;
    for(int i = 1; i <= n; i ++){
        int maxv = 1;
        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], maxv);
            if(b[j] < a[i])     maxv = max(maxv, f[i][j] + 1);
        }
    }
    for(int i = 1; i <= n; i ++)    res = max(res, f[n][i]);
    cout << res << endl;

    return 0;
}