fabs(double)
abs(int)

数字三角形模型

1018.最低通行费用

一个商人穿过一个 N×N 的正方形的网格，去参加一个非常重要的商务活动。
他要从网格的左上角进，右下角出。
每穿越中间 1 个小方格，都要花费 1 个单位时间。
商人必须在 (2N−1) 个单位时间穿越出去。
而在经过中间的每个小方格时，都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用？
注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。
输入格式
第一行是一个整数，表示正方形的宽度 N。
后面 N 行，每行 N 个不大于 100 的正整数，为网格上每个小方格的费用。
输出格式
输出一个整数，表示至少需要的费用。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int g[N][N],f[N][N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            cin >> g[i][j];
        }
    }
    memset(f, 0x3f, sizeof f); 
    f[1][1] = g[1][1];
    // 注意这里初始化的作用
    /*因为要取最小值，所以把不合法状态全部初始未正无穷，只能从f[1][1]出发*/
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            if(i==1&&j==1){
                continue;
            }
            f[i][j] = min(f[i][j-1],f[i-1][j])+g[i][j];
        }
    }
    cout << f[n][n];
}

1027. 方格取数

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

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。
在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
输入格式
第一行为一个整数N，表示 N×N 的方格图。
接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。
行和列编号从 1 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数，表示两条路径上取得的最大的和。

#include <iostream>
using namespace std;
const int N = 15;
int n;
int w[N][N], f[N*2][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 <= 2*n; k++) {
        for(int i1 = 1; i1 <= n; i1++) {
            for(int i2 = 1; i2 <= n; i2++) {
                int j1 = k-i1, j2 = k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n) {
                    // 不能越界
                    int &x = f[k][i1][i2];
                    int t = w[i1][j1];
                    if(i1!=i2) t += w[i2][j2];
                    //不重合则需要加两个权重.
                    x = max(x, f[k-1][i1-1][i2-1]+t);
                    x = max(x, f[k-1][i1-1][i2]+t);
                    x = max(x, f[k-1][i1][i2-1]+t);
                    x = max(x, f[k-1][i1][i2]+t);
                    //保留最大属性
                }
            }
        }
    }
    cout << f[n*2][n][n] << endl;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int g[N][N];
int f[N*2][N][N];
int main()
{
    int n;
    cin >> n;
    int x,y,w;
    while(cin>>x>>y>>w&&(x||y||w)){
        g[x][y] = w;
    }
    for (int i = 2; i <= 2*n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            for (int k = j; k <= n; k ++ ){ // 这里也可以写成k从j开始
                if(i>=j&&i>=k){
                    auto& t = f[i][j][k];
                    t = max(t,f[i-1][j][k]);
                    t = max(t,f[i-1][j-1][k-1]);
                    t = max(t,f[i-1][j-1][k]);
                    t = max(t,f[i-1][j][k-1]);
                    t += g[j][i-j];
                    if(j!=k){
                        t += g[k][i-k];
                    }
                }
            }
        }
    }
    cout <<f[2*n][n][n];
}

275. 传纸条

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

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int g[N][N];
int f[N*2][N][N];
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            cin >> g[i][j];
        }
    }
 /*这道题与上一题不同的地方有两点
     1. 上题是走过A点之后，A点的值变为0，但是第二次还可以走
         但是这道题是走过之后就不能走了
     2. 本题的n和m不一样，上题是一个n*n的矩阵
 */
    int sum = max(n,m);
    for (int i = 2; i <= 2*sum; i ++ ){
        for (int j = 1; j <= sum; j ++ ){
            for (int k = j+1; k <= sum; k ++ ){ //  这里直接从j+1开始，因为k!=j
                if(i>=j&&i>=k&&j!=k){
                    auto& t = f[i][j][k];
                    t = max(t,f[i-1][j][k]);
                    t = max(t,f[i-1][j-1][k-1]);
                    t = max(t,f[i-1][j-1][k]);
                    t = max(t,f[i-1][j][k-1]);
                    t += g[j][i-j]+g[k][i-k];
                }
            }
        }
    }
    cout << f[2*sum][sum-1][sum]<<endl;
}

这里我想解释一下为什么k可以从j+1开始 首先要明确 f[i][j][k] 表示的是什么呢 ，表示两个点 a1=(j,i-j),a2=(k,i-k); 也就是说表示的是两个点横纵坐标之和是i，其中一个的横坐标的j，另一个的横坐标是k 那为什么k可以从j+1开始呢?

1. j!=k

1. 就拿这个样例来模拟一下
   1. f[3][1][2] = max(f[2][1][2],f[2][0][2],f[2][0][1],f[2][1][1]) + g[1][3-1] + g[2][3-2]
   2. f[3][2][1] = max(f[2][2][1],f[2][1][1],f[2][1][0],f[2][2][0]) + g[1][3-1] + g[2][3-2]
      1. 可以看到后面两项完全相同，只是前面的项不同而已，但是前面的项全部为0，
      2. 这就推出f[3][1][2]和f[3][2][1]两项是等同的
      3. 而f[4]又使用的f[3]的结果所以f[4]也是可以的以此类推

这样说似乎有点抽象，画个图来说明 在计算f[4][1][3]的时候 会从5的上下来枚举，9的上下来枚举 然后 + 5 + 9 f[4][3][1]的时候也同样会，这样想似乎更好理解

最长上升子序列模型

1014. 登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。
同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。
队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？
输入格式
第一行包含整数N，表示景点数量。
第二行包含N个整数，表示每个景点的海拔。
输出格式
输出一个整数，表示最多能浏览的景点数。
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N];
int f[N],g[N];
int n;
void get(int b[N]){
    for (int i = 1; i <= n; i ++ ){
        b[i] = 1;
        for (int j = 1; j < i; j ++ ){
            if(a[i]>a[j]){
                b[i] = max(b[i],b[j]+1);
            }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    get(f);
    reverse(a+1,a+n+1);
    get(g);
    reverse(g+1,g+n+1); // 这里的g也要反转
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        res = max(f[i]+g[i]-1,res);
    }
    cout << res;
}

482. 合唱队形

N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。
合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK，  则他们的身高满足 T1<…Ti+1>…>TK(1≤i≤K)。
你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数 N，表示同学的总数。
第二行有 N 个整数，用空格分隔，第 i 个整数 Ti 是第 i 位同学的身高(厘米)。
输出格式
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

只需要将1014登山的最后输出改为
cout<< n- res;
即可

1012. 友好城市

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。
北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。
每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。
编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。
输入格式
第1行，一个整数N，表示城市数。
第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。
输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

// 只需要对一方的城市排序
// 然后对另一方求最长递增子序列
#include<iostream>
#include<algorithm>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
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[i].y>a[j].y){
                f[i] = max(f[i],f[j]+1);
            }
            res = max(res,f[i]);
        }
    }
    cout << res;
}

1010. 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
const int N = 1010;
int a[N],n;
int f[N],g[N];
int main()
{
    string str;
    getline(cin,str);
    stringstream ssin(str);
    while(ssin>>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[i]<=a[j]){
                f[i] = max(f[i],f[j]+1);
            }
            res = max(f[i],res);
        }
    }
    // 贪心解法求，
    // 从头开始遍历，每次将a[i] 加入当前所有导弹中最小的后面
    // g[i]中是一个递增序列
    int cnt = 0;
    for (int i = 0; i < n; i ++ ){
        int k=0;
        while(k<cnt&&a[i]>g[k])k++;
        g[k] = a[i];
        if(k>=cnt){
            cnt++;
        }
    }
    cout << res <<endl;
    cout << cnt;
}

187. 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。
第二行包含 n 个不同的整数，表示每个导弹的高度。
当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。
输入样例：
5
3 5 2 4 1
0
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为 3,4 的导弹，另一套击落高度为 5,2,1 的导弹。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int a[N];
int up[N],down[N];
int n,ans;
void dfs(int u,int su,int sd){ // 上升子序列，下降子序列
    if(su+sd>=ans){
        return;
    }
    if(u==n){
        ans = su+sd;
        return;
    }
    // 枚举将点u放到上升子序列
    int k=0;
    while(k<su&&up[k]>=a[u]){
        k++;
    }
    int t = up[k];
    up[k] = a[u];
    if(k>=su){
        dfs(u+1,su+1,sd);
    }else{
        dfs(u+1,su,sd);
    }
    // 恢复现场
    up[k] = t;
    // 枚举将点u放到下降子序列
    k=0;
    while(k<sd&&down[k]<=a[u]){
        k++;
    }
    t = down[k];
    down[k] = a[u];
    if(k>=sd){
        dfs(u+1,su,sd+1);
    }else{
        dfs(u+1,su,sd);
    }
    // 恢复现场
    down[k] = t;
}
int main()
{
    while(cin>>n&&n){
        for (int i = 0; i < n; i ++ ){
            cin >> a[i];
        }
        ans = n;
        dfs(0,0,0);
        cout << ans <<endl;
    }
}、‘

272. 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
输入格式
第一行包含一个整数 N，表示数列 A，B 的长度。
第二行包含 N 个整数，表示数列 A。
第三行包含 N 个整数，表示数列 B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N],b[N];
int f[N][N];  // 只考虑a的前i个字符，以b[j]结尾的最长公共子序列
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++ ){
        cin >> b[i];
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= n; j ++ ){
            // 相当于不考虑a[i], 就是说如果a[i]!=b[j]的话，不用考虑a[i]
            // 那么如果考虑a[i]的话以b[j]结尾的方案一定是大于等于不考虑a[i]的方案的
            f[i][j] = f[i-1][j]; 
            if(a[i]==b[j]){ 
                // 他们俩相等了，那么就以b[j]结尾的公共子序列最小是1
                f[i][j] = max(f[i][j],1);
                for (int k = 0; k < j; k ++ ){
                    // 因为是上升子序列，a[i]和b[j]也是相等的，那么前面的就一定得
                    // 比他们小
                    if(b[k]<b[j]){
                        f[i][j] = max(f[i][j],f[i][k]+1);
                    }
                }   
            }
            res = max(res,f[i][j]);
        }
    }
    cout << res;
}
// 优化版本
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N],b[N];
int f[N][N];  // 只考虑a的前i个字符，以b[j]结尾的最长公共子序列
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++ ){
        cin >> b[i];
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        int maxv = 1;
        for (int j = 1; j <= n; j ++ ){
            // 不考虑a[i]
            f[i][j] = f[i-1][j];
            if(a[i]==b[j]){
                f[i][j] = max(f[i][j],maxv);
            }
            if(a[i]>b[j]){
                maxv = max(maxv,f[i][j]+1);
            }
            res = max(res,f[i][j]);
        }
    }
    cout << res;
}

背包模型

1022. 宠物小精灵之收服

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。
小智也想收服其中的一些小精灵。
然而，野生的小精灵并不那么容易被收服。
对每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。
当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。
当小智的精灵球用完时，狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。
如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。
小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。
请问，小智该如何选择收服哪些小精灵以达到他的目标呢？
输入格式
输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。
之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
输出格式
输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
输入样例1：
10 100 5
7 10
2 40
2 50
1 20
4 20
输出样例1：
3 30
输入样例2：
10 100 5
8 110
12 10
20 10
5 200
1 110
输出样例2：
0 100

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,M= 510,K=110;
int f[N][M];
int a[K],b[K];
int main()
{
    int n,m,z;
    cin >> n >> m >> z; // 精灵球数量、皮卡丘初始的体力值
    for (int i = 1; i <= z; i ++ ){
        cin >> a[i] >> b[i];
        // 收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。
    }
    for (int i = 1; i <= z; i ++ ){
        for (int j = n; j>=a[i] ; j-- ){
            for (int k = m-1; k>=b[i] ; k -- ){  // 注意这里是m-1 不能到m
                f[j][k] = max(f[j][k],f[j-a[i]][k-b[i]]+1);
            }
        }
    }
    cout << f[n][m-1];
    int used=0;
    for (int i = 0; i <m; i ++ ){
        if(f[n][i]==f[n][m-1]){
            used = i;
            break;
        }
    }
    cout << " "<<m - used;
}

4378. 选取数对

输入格式
第一行包含三个整数 n,m,k。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示 sum 的最大可能值。
数据范围

输入样例1：
5 2 1
1 2 3 4 5
输出样例1：
9
输入样例2：
7 1 3
2 10 7 18 5 33 0
输出样例2：
61

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,m,k;
const int N = 5010;
LL s[N];
LL f[N][N];
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ){
        cin >> s[i];
        s[i]+=s[i-1];
    }
    for (int i = m; i <= n; i ++ ){
        for (int j = 1; j <= k; j++ ){   // 这里的i-m太妙了
            f[i][j]= max(f[i-1][j],f[i-m][j-1]+s[i]- s[i-m]);
        }
    }
    cout << f[n][k];
}

278. 数字组合

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。
输入格式
第一行包含两个整数 N 和 M。
第二行包含 N 个整数，表示 A1,A2,…,AN。
输出格式
包含一个整数，表示可选方案数。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,M = 1e4+10;
int f[M];
int a[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    f[0]=1;
    for (int i = 1; i <= n; i ++ ){
        for (int j = m; j >= a[i] ; j -- ){
            f[j] += f[j-a[i]];
        }
    }
    cout << f[m] ;
}

1023. 买书

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。
问小明有多少种买书方案？（每种书可购买多本）
输入格式
一个整数 n，代表总共钱数。
输出格式
一个整数，代表选择方案种数。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int a[5]={10,20,50,100};
int main()
{
    int n;
    cin >> n;
    f[0]=1;
    for (int i = 0; i < 4; i ++ ){
        for (int j = a[i]; j <= n; j ++ ){
            f[j] += f[j-a[i]];
        }
    }
    cout << f[n];
}

1021. 货币系统

给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
输入格式
第一行，包含两个整数n和m。
接下来n行，每行包含一个整数，表示一种货币的面值。
输出格式
共一行，包含一个整数，表示方案数。
输入样例：
3 10
1
2
5
输出样例：
10

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3010;
int a[N];
LL f[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i];
    }
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ){
        for (int j = a[i]; j <= m; j ++ ){
            f[j] += f[j-a[i]];
        }
    }
    cout << f[m];
}

532. 货币系统

在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。
为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。
在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]×t[i] 的和为 x。
然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。
例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。
两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。
他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。
他们希望你来协助完成这个艰巨的任务：找到最小的 m。
输入格式
输入文件的第一行包含一个整数 T，表示数据的组数。
接下来按照如下格式分别给出 T 组数据。
每组数据的第一行包含一个正整数 n。
接下来一行包含 n 个由空格隔开的正整数 a[i]。
输出格式
输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。
输入样例：
2
4
3 19 10 6
5
11 29 13 19 17
输出样例：
2
5

// 先排序从前向后找，如果当前数不能被前边得数表示出来，那么就一定得选当前数
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,M=25010;
int a[N];
bool f[M];
int main()
{
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++ ){
            cin >> a[i];
        }
        sort(a,a+n);
        memset(f, 0, sizeof f);
        f[0]=true;
        int res=0;
        for (int i = 0; i < n; i ++ ){
            if(f[a[i]]){
                res++;
            }
            for (int j = a[i]; j <=a[n-1]; j ++ ){
                f[j]|=f[j-a[i]];
            }
        }
        cout << n-res<<endl;
    }
}

1019. 庆功会

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。
期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。
输入格式
第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。
接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。
输出格式
一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。
输入样例：
5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1
输出样例：
1040

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 60010,M=6010;
LL w[N],v[N];
LL f[M];
int main()
{
    int n,m;
    cin >> n >> m;
    int cnt=0;
    for (int i = 0; i < n; i ++ ){
        int ww,vv,s; // 价格，价值，最大数量
        cin >> ww >> vv >> s;
        int k=1;
        while(k<=s){
            w[cnt]=ww*k;
            v[cnt]=vv*k;
            s-=k;
            k*=2;
            cnt++;
        }
        if(s>0){
            w[cnt]=ww*s;
            v[cnt]=vv*s;
            cnt++;
        }
    }
    for (int i = 0; i < cnt; i ++ ){
        for (int j = m; j >= w[i]; j -- ){
            f[j] = max(f[j],f[j-w[i]]+v[i]);
        }
    }
    cout << f[m];
}

7. 混合背包问题

有 N 种物品和一个容量是 V 的背包。
物品一共有三类：
第一类物品只能用1次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 si 次（多重背包）；
每种体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
si=−1 表示第 i 种物品只能用1次；
si=0 表示第 i 种物品可以用无限次；
si>0 表示第 i 种物品可以使用 si 次；
输出格式
输出一个整数，表示最大价值。
输入样例
4 5
1 2 -1
2 4 1
3 4 0
4 5 2
输出样例：
8

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 60010,M=6010;
LL w[N],v[N];
LL f[M];
int w1[N],v1[N];
int main()
{
    int n,m;
    cin >> n >> m;
    int cnt=0,sum=0;
    for (int i = 0; i < n; i ++ ){
        int ww,vv,s; // 价格，价值，最大数量
        cin >> ww >> vv >> s;
        if(s==-1){
            w[cnt]=ww;
            v[cnt]=vv;
            cnt++;
        }
        if(s==0){
            w1[sum]=ww;
            v1[sum]=vv;
            sum++;
        }
        if(s>0){
            int k=1;
            while(k<=s){
                w[cnt]=ww*k;
                v[cnt]=vv*k;
                s-=k;
                k*=2;
                cnt++;
            }
            if(s>0){
                w[cnt]=ww*s;
                v[cnt]=vv*s;
                cnt++;
            }
        }
    }
    for (int i = 0; i < cnt; i ++ ){
        for (int j = m; j >= w[i]; j -- ){
            f[j] = max(f[j],f[j-w[i]]+v[i]);
        }
    }
    for (int i = 0; i < sum; i ++ ){
        for (int j = w1[i]; j<=m; j ++ ){
            f[j] = max(f[j],f[j-w1[i]]+v1[i]);
        }
    }
    cout << f[m];
}

8. 二维费用的背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。
每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。
输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。
接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。
输出格式
输出一个整数，表示最大价值。
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,V = 110,M=110;
int vv[N],mm[N],ww[N];
int f[V][M];
int main()
{
    int n,v,m;
    cin >> n >> v >> m;
    for (int i = 0; i < n; i ++ ){
        cin >> vv[i] >> mm[i] >> ww[i];
    }
    for (int i = 0; i < n; i ++ ){
        for(int j=v;j>=vv[i];j--){
            for(int k=m;k>=mm[i];k--){
                f[j][k] = max(f[j][k],f[j-vv[i]][k-mm[i]]+ww[i]);
            }
        }
    }
    cout << f[v][m];
}

1020. 潜水员

潜水员为了潜水要使用特殊的装备。
他有一个带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 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。
输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1010;
int a[N],b[N],c[N]; //氧和氮的容量及气缸重量。
int f[25][85];
int main()
{
    int n,m,z;
    cin >> n >> m >> z;
    for (int i = 0; i < z; i ++ ){
        cin >> a[i] >> b[i] >> c[i];
    }
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 0; i < z; i ++ ){
        for (int j = n; j>=0 ; j -- ){
            for (int k = m; k>=0 ; k -- ){ // 注意是大于等于0
                f[j][k] = min(f[j][k],f[max(0,j-a[i])][max(0,k-b[i])]+c[i]);
                // 这里是关键
            }
        }
    }
    cout << f[n][m];
}

1013.机器分配

总公司拥有M台 相同 的高效设备，准备分给下属的N个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。盈利与分配的设备数量有关。
问：如何分配这M台设备才能使国家得到的盈利最大？
求出最大盈利值。
分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M。
输入格式
第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；
接下来是一个NM的矩阵，矩阵中的第 i 行第 j 列的整数表示第 i 个公司分配 j 台机器时的盈利。
输出格式
第一行输出最大盈利值；
接下N行，每行有2个数，即分公司编号和该分公司获得设备台数。
答案不唯一，输出任意合法方案即可。
输入样例：
3 3
30 40 50
20 30 50
20 25 30
*输出样例：
70
1 1
2 1
3 1

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 12,M = 17;
using namespace std;
int g[N][M];
int res[N],tmp[N];
int maxv;
int n,m;
void dfs(int x,int last,int value){ // 当前分配到第i家公司，剩余可分配数，当前最大价值
    if(x==n+1){
        if(value>maxv){
            for (int i = 1; i <= n; i ++ ){
                res[i] = tmp[i];
            }
            maxv = value;
        }
        return;
    }
    for (int i = 0; i <= last; i ++ ){
        tmp[x] = i;
        value+=g[x][i];
        dfs(x+1,last-i,value);
        value-=g[x][i];
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            cin >> g[i][j];
        }
    }
    dfs(1,m,0);
    cout << maxv<<endl;
    for (int i = 1; i <= n; i ++ ){
        cout << i << " "<<res[i]<<endl;
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 12,M = 17;
using namespace std;
int g[N][M],f[N][M];
int res[N],tmp[N];
int maxv;
int n,m;
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            cin >> g[i][j];
        }
    }
    for (int i = 1; i <= n; i ++ ){ // 物品
        for (int j = 1; j <= m; j ++ ){ // 体积
            f[i][j] = f[i-1][j];
            for (int k = 1; k <= j; k ++ ){ // j决策 选物品组的第几个物品
                f[i][j] = max(f[i][j],f[i-1][j-k]+g[i][k]);
            }            
        }
    }
    int i=n,j=m;
    while(i&&j){
        for (int k = 0; k <= m; k ++ ){
            if(f[i][j]==f[i-1][j-k]+g[i][k]){
                res[i] = k;
                j = j-k;
                i--;
                break;
            }
        }
    }
    cout << f[n][m] <<endl;
    for (int i = 1; i <= n; i ++ ){
        cout << i <<" "<<res[i]<<endl;
    }
}

426. 开心的金明

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。
更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”
今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。
于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。
他还从因特网上查到了每件物品的价格（都是整数元）。
他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为：
v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]
请帮助金明设计一个满足要求的购物单。
输入格式
输入文件的第 1 行，为两个正整数 N 和 m，用一个空格隔开。（其中 N 表示总钱数，m 为希望购买物品的个数）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v 和 p。（其中 v 表示该物品的价格，p 表示该物品的重要度）
输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 108）。
输入样例：
1000 5
800 2
400 5
300 5
400 3
200 2
输出样例：
3900

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e5+10,M = 30;
int f[N];
int n,m;
int ww[M],vv[M]; // 价值，体积
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ){
        int v,p;
        cin >> v >> p;
        ww[i] = v*p;
        vv[i] = v;
    }
    for (int i = 1; i <=m; i ++ ){
        for (int j = n; j >=vv[i]; j -- ){
            f[j] = max(f[j],f[j-vv[i]]+ww[i]);
        }
    }
    cout << f[n];
}