题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 $1 … N$。

输入格式

第一行两个整数，$N，V$，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式

输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。

物品编号范围是 $1 … N$。

数据范围

$0 \lt N, V \le 1000$
$0\lt v_i, w_i \le 1000$

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

1 4

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int f[N][N];
int n , m;
int v[N] , w[N];

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

    for(int i = n ; i >= 1 ; i -- )
        for(int j = 0 ; j <= m ; j ++ )
        {
            f[i][j] = f[i + 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j] , f[i + 1][j - v[i]] + w[i]);
        }

    int j = m;
    for(int i = 1 ; i <= n ; i ++ )
        if(j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << ' ';
            j -= v[i];
        }

    return 0;
}

题目描述

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119

如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

第一行有2个整数 $m，n$。它们表示氧，氮各自需要的量。

第二行为整数 $k$ 表示气缸的个数。

此后的 $k$ 行，每行包括$a_i，b_i，c_i$，3个整数。这些各自是：第 $i$ 个气缸里的氧和氮的容量及气缸重量。

输出格式

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围

$1 \le m \le 21$,
$1 \le n \le 79$,
$1 \le k \le 1000$,
$1 \le a_i \le 21$,
$1 \le b_i \le 79$,
$1 \le c_i \le 800$

输入样例：

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

输出样例：

249

// 最多 : f[0][i] = 0 , 不选物品,体积最多是i的方案存在,重量为0
// 恰好 : f[0][0] = 0 , 不选物品,体积只能是0的方案存在,重量为0
// 最少 : f[0][<=0] = 0 , 不选物品,体积最少是<=0的方案存在,重量为0

#include <iostream>
#include <cstring>

using namespace std;

const int N = 22 , M = 80;
int f[N][M];
int n , m , k;

int main()
{
    cin >> n >> m >> k;

    memset(f , 0x3f , sizeof f);
    f[0][0] = 0;
    while(k -- )
    {
        int v1 , v2 , w;
        cin >> v1 >> v2 >> w;
        for(int i = n ; i >= 0 ; i -- )
            for(int j = m ; j >= 0 ;  j -- )
                f[i][j] = min(f[i][j] , f[max(0 , i - v1)][max(0 , j - v2)] + w);
    }

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

    return 0;
}

题目描述

有 $N$ 件物品和一个容量是 $V$ 的背包，背包能承受的最大重量是 $M$。

每件物品只能用一次。体积是 $v_i$，重量是 $m_i$，价值是 $w_i$。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式

第一行三个整数，$N,V, M$，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 $N$ 行，每行三个整数 $v_i, m_i, w_i$，用空格隔开，分别表示第 $i$ 件物品的体积、重量和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

$0 \lt N \le 1000$
$0 \lt V, M \le 100$
$0 \lt v_i, m_i \le 100$
$0 \lt w_i \le 1000$

输入样例

4 5 6
1 2 3
2 4 4
3 4 5
4 5 6

输出样例：

8

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010 , V = 110 , M = 110;
int f[N][V][M];
int n , v , m;

int main()
{
    cin >> n >> v >> m;

    for(int i = 1 ; i <= n ; i ++ )
    {
        int a , b , c;
        cin >> a >> b >> c;

        for(int j = 0 ; j <= v ; j ++ )
            for(int k = 0 ; k <= m ; k ++ )
            {
                f[i][j][k] = f[i - 1][j][k];
                if(j >= a && k >= b)
                f[i][j][k] = max(f[i][j][k] , f[i - 1][j - a][k - b] + c);
            }
    }

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

    return 0;
}

题目描述

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。

期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

输入格式

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。

接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

输出格式

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

数据范围

$n \le 500, m \le 6000$,
$v \le 100, w \le 1000, s \le 10$

输入样例：

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例：

1040

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510 , M = 6010;
int f[N][M];
int n , m;

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i ++ )
    {
        int v , w , s;
        cin >> v >> w >> s;

        for(int j = 0 ; j <= m ; j ++ )
            for(int k = 0 ; k <= s && k * v <= j ; k ++ )
                f[i][j] = max(f[i][j] , f[i - 1][j - k * v] + k * w);
    }

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

    return 0;
}

题目描述

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式

一个整数 n，代表总共钱数。

输出格式

一个整数，代表选择方案种数。

数据范围

$0 \le n \le 1000$

输入样例1：

20

输出样例1：

2

输入样例2：

15

输出样例2：

0

输入样例3：

0

输出样例3：

1

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;
int f[N];
int v[4] = {10 , 20 , 50 , 100};

int main()
{
    int n;
    cin >> n;
    f[0] = 1;
    for(int i = 0 ; i < 4 ; i ++ )
        for(int j = v[i] ; j <= n ; j ++ )
            f[j] += f[j - v[i]];

    cout << f[n] << endl;

    return 0;
}

题目描述

给定 $N$ 个正整数 $A_1,A_2,…,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，表示 $A_1,A_2,…,A_N$。

输出格式

包含一个整数，表示可选方案数。

数据范围

$1 \le N \le 100$,
$1 \le M \le 10000$,
$1 \le A_i \le 1000$,
答案保证在 int 范围内。

输入样例：

4 4
1 1 2 2

输出样例：

3

朴素版

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110 , M = 10010;
int f[N][M];

int main()
{
    int n , m;
    cin >> n >> m;

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

    for(int i = 1 ; i <= n ; i ++ )
    {
        int v;
        cin >> v;
        for(int j = 0 ; j <= m ; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(j >= v) f[i][j] += f[i - 1][j - v];
        }
    }

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

    return 0;
}

优化版

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;
int f[N];

int main()
{
    int n , m;
    cin >> n >> m;

    f[0] = 1;

    while(n -- )
    {
        int v;
        cin >> v;
        for(int j = m ; j >= v ; j -- ) f[j] += f[j - v];
    }

    cout << f[m] << endl;

    return 0;
}

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

$0 < V \le 20000$,
$0 < n \le 30$

输入样例：

24
6
8
3
12
7
9
7

输出样例：

0

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

using namespace std;

const int N = 35 , M = 20010;
int v[N];
int V , n;
int f[N][M];

int main()
{
    cin >> V >> n;

    for(int i = 1 ; i <= n ; i ++ ) cin >> v[i];

    for(int i = 1 ; i <= n ; i ++ )
        for(int j = 0 ; j <= V ; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(v[i] <= j) f[i][j] = max(f[i][j] , f[i - 1][j - v[i]] + v[i]);
        }

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

    return 0;
}

题目描述

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

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

输入样例：

4
2 2 1 3
2 1 2 3

输出样例：

2

未优化

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

using namespace std;

const int N = 3010;
int a[N] , b[N];
int f[N][N];
int n;

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

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

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

    cout << res << endl;

    return 0;
}

优化版本

#include <iostream>
#include <cstring>

using namespace std;

const int N = 3010;
int a[N] , b[N];
int f[N][N];
int n;

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

    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 - 1][j] + 1);
        }
    }

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

    cout << res << endl;

    return 0;
}

题目描述

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

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

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

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

输入格式

输入包含多组测试用例。

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

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

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

输出格式

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

数据范围

$1 \le n \le 50$

输入样例：

5
3 5 2 4 1
0

输出样例：

2

样例解释

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

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

全局变量记录最小值

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

using namespace std;

const int N = 60;
int n , ans;
int down[N] , up[N];
int h[N];

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

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

    k = 0;
    while(k < sd && down[k] <= h[u]) k ++;
    t = down[k];
    down[k] = h[u];
    if(k < sd) dfs(u + 1 , su , sd);
    else dfs(u + 1 , su , sd + 1);
    down[k] = t;
}

int main()
{
    while(cin >> n , n)
    {
        for(int i = 0 ; i < n ; i ++ ) cin >> h[i];

        ans = n;
        dfs(0 , 0 , 0);

        cout << ans << endl;
    }
    return 0;
}

迭代加深

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

using namespace std;

const int N = 60;
int up[N] , down[N];
int h[N];
int n;

bool dfs(int depth , int u , int su , int sd)
{
    if(su + sd > depth) return false;
    if(u == n) return true;

    bool flag = false;
    for(int i = 1 ; i <= su ; i ++)
        if(up[i] < h[u])
        {
            int t = up[i];
            up[i] = h[u];
            if(dfs(depth , u + 1 , su , sd)) return true;
            up[i] = t;
            flag = true;
            break;
        }
    if(!flag)
    {
        up[su + 1] = h[u];
        if(dfs(depth , u + 1 , su + 1 , sd)) return true;
    }

    flag = false;
    for(int i = 1 ; i <= sd ; i ++ )
        if(down[i] > h[u])
        {
            int t = down[i];
            down[i] = h[u];
            if(dfs(depth , u + 1 , su , sd)) return true;
            down[i] = t;
            flag = true;
            break;
        }
    if(!flag)
    {
        down[sd + 1] = h[u];
        if(dfs(depth , u + 1 , su , sd + 1)) return true;
    }

    return false;
}

int main()
{
    while(cin >> n , n)
    {
        for(int i = 0 ; i < n ; i ++ ) cin >> h[i];

        int depth = 0;
        while(!dfs(depth , 0 , 0 , 0)) depth ++;

        cout << depth << endl;
    }
    return 0;
}

题目描述

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 $m$ 行 $n$ 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 $(1,1)$，小轩坐在矩阵的右下角，坐标 $(m,n)$。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 $0$ 表示），可以用一个 $0 \sim 100$ 的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式

第一行有 $2$ 个用空格隔开的整数 $m$ 和 $n$，表示学生矩阵有 $m$ 行 $n$ 列。

接下来的 $m$ 行是一个 $m \times n$ 的矩阵，矩阵中第 $i$ 行 $j$ 列的整数表示坐在第 $i$ 行 $j$ 列的学生的好心程度，每行的 $n$ 个整数之间用空格隔开。

输出格式

输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围

$1 \le n,m \le 50$

输入样例：

3 3
0 3 9
2 8 5
5 7 0

输出样例：

34

DP

O(n ^ 3)

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

using namespace std;

const int N = 60;
int f[2 * N][N][N] , w[N][N];
int n , m;

int main()
{
    cin >> n >> m;

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

    for(int k = 2 ; k <= n + m ; k ++ )
        for(int i1 = max(1 , k - m) ; i1 <= min(n , k - 1) ; i1 ++ )
            for(int i2 = max(1 , k - m) ; i2 <= min(n , k - 1) ; i2 ++ )
                {
                    int j1 = k - i1 , j2 = k - i2;
                    int t = w[i1][j1];
                    if(i1 != i2) t += w[i2][j2];
                    for(int a = 0 ; a <= 1 ; a ++ )
                        for(int b = 0 ; b <= 1 ; b ++ )
                            f[k][i1][i2] = max(f[k][i1][i2] , f[k - 1][i1 - a][i2 - b] + t);
                }

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

    return 0;
}