AcWing-算法提高课（第一章）-上

数字三角形模型

摘花生

• 状态表示：f[i,j]（f[i,j]表示，在，由，从左上角走到(i,j)这个结点的每条路径的路径上所有结点的数字之和，组成的集合，中，的最大值）
• 状态计算：f[i,j]=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j])（a[i,j]表示(i,j)这个结点的数字）

摘花生

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];// 状态表示
int w[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)// n次询问
    {
        int r, c;
        scanf("%d %d", &r, &c);
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                scanf("%d", &w[i][j]);
        
        // 状态计算
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                f[i][j] = max(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j]);
                
        printf("%d\n", f[r][c]);
    }
    return 0;
}

最低通行费

• 状态表示：f[i,j]（f[i,j]表示，在，由，从左上角走到(i,j)这个结点的每条路径的路径上所有结点的数字之和，组成的集合，中，的最大值）
• 状态计算：f[i,j]=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j])（a[i,j]表示(i,j)这个结点的数字）

最低通行费

#include <iostream>

using namespace std;

const int N = 110;

int w[N][N];
int f[N][N];// 状态表示

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &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] = 0x3f3f3f3f;
                if (i > 1)
                    // 大于第1行时，才可能会从上面走过来
                    f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                if (j > 1)
                    // 大于第1列时，才可能会从左边走过来
                    f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }
            
    printf("%d\n", f[n][n]);
    return 0;
}

方格取数

• 状态表示：f[k,i1,i2]（f[k,i1,i2]表示，从左上角分别走到(i1,k-i1)和(i2,k-i2)这两个结点的两次路线走法的，在，由，每次路线走法的每条路径的路径上所有结点的数字之和，组成的集合，中，对应的最大值，相加后的结果）
• 状态计算：f[k,i1,i2]=max(f[k-1,i1-1,i2-1]+a[i1,k-i1]+a[i2,k-i2],f[k-1,i1-1,i2]+a[i1,k-i1]+a[i2,k-i2],f[k-1,i1,i2-1]+a[i1,k-i1]+a[i2,k-i2],f[k-1,i1,i2]+a[i1,k-i1]+a[i2,k-i2])（其中，k为横纵坐标之和）

方格取数

#include <iostream>

using namespace std;

const int N = 15;

int f[2 * N][N][N];// 状态表示
int w[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    
    int r, c, x;
    while (cin >> r >> c >> x, r || c || x)
        w[r][c] = x;
        
    // 状态计算
    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)// j1和j2必须在正确的范围内
                {
                    int t = w[i1][j1];
                    
                    // 同一个方格中的数字只能取一次
                    
                    if (i1 != i2)
                        t += w[i2][j2];
                        
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t);
                }
            }
            
    printf("%d\n", f[n + n][n][n]);
    
    return 0;
}

最长上升子序列模型

怪盗基德的滑翔翼

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个上升子序列的长度，组成的集合，中，的最大值）
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个下降子序列的长度，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+1)（其中，j∈{1,2,…,i-1}）

怪盗基德的滑翔翼

#include <iostream>

using namespace std;

const int N = 110;

int f[N];// 状态表示
int a[N];

int main()
{
    int k;
    scanf("%d", &k);
    while (k--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
            
        int res = 0;
        
        // 状态计算
        for (int i = 1; i <= n; i++)
        {
            f[i] = 1;
            for (int j = 1; j <= i - 1; 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 - 1; j++)
                if (a[j] > a[i])// 最长下降子序列
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        
        printf("%d\n", res);
    }
    return 0;
}

登山

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个上升子序列的长度，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+1)（其中，j∈{1,2,…,i-1}）

登山

#include <iostream>

using namespace std;

const int N = 1100;

int ful[N];// 状态表示
int fur[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    // 状态计算    
    for (int i = 1; i <= n; i++)
    {
        ful[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])// 从左到右的最长上升子序列
                ful[i] = max(ful[i], ful[j] + 1);
    }
    
    // 状态计算
    for (int i = n; i >= 1; i--)
    {
        fur[i] = 1;
        for (int j = n; j >= i + 1; j--)
            if (a[j] < a[i])// 从右到左的最长上升子序列
                fur[i] = max(fur[i], fur[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, ful[i] + fur[i] - 1);
        
    printf("%d\n", res);
    return 0;
}

合唱队形

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个上升子序列的长度，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+1)（其中，j∈{1,2,…,i-1}）

合唱队形

#include <iostream>

using namespace std;

const int N = 110;

int ful[N];// 状态表示
int fur[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        
    // 状态计算  
    for (int i = 1; i <= n; i++)
    {
        ful[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])// 从左到右的最长上升子序列
                ful[i] = max(ful[i], ful[j] + 1);
    }
    
    // 状态计算  
    for (int i = n; i >= 1; i--)
    {
        fur[i] = 1;
        for (int j = n; j >= i + 1; j--)
            if (a[j] < a[i])// 从右到左的最长上升子序列
                fur[i] = max(fur[i], fur[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, ful[i] + fur[i] - 1);
        
    printf("%d\n", n - res);
    return 0;
}

友好城市

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个上升子序列的长度，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+1)（其中，j∈{1,2,…,i-1}）

友好城市

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int f[N];// 状态表示
pair<int, int> a[N];

int main()
{
    int n;
    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);
    
    int res = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j].second < a[i].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    return 0;
}

最大上升子序列和

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个上升子序列的数字之和，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+a[i])（其中，j∈{1,2,…,i-1}）

最大上升子序列和

#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int f[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        
    int res = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + a[i]);
                
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    return 0;
}

拦截导弹

• 状态表示：
  • f[i]（f[i]表示，在，由，以第i个数结尾的每个下降子序列的长度，组成的集合，中，的最大值）
• 状态计算：f[i]=max(f[j]+1)（其中，j∈{1,2,…,i-1}）

拦截导弹

#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int f[N], a[N];
int dd[N];// 存储的是当前每个非上升子序列的末尾值

int main()
{
    int n = 0;
    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]);
    }
    
    // 第二个问题用贪心的思路进行思考
    int cnt = 0;// 存储的是非上升子序列的个数
    for (int i = 0; i < n; i++)
    {
        int k = 0;// 从第0个非上升子序列开始遍历
        
        // 当没有遍历完非上升子序列，并且当前非上升子序列的末尾值小于当前元素，则需要继续遍历
        while (k < cnt && dd[k] < a[i])
            k++;
            
        dd[k] = a[i];
        
        if (k == cnt)// 这是需要单独开辟一个非上升子序列的情况
            cnt++;// 非上升子序列的个数加1
    }
    
    printf("%d\n%d\n", res, cnt);
    
    return 0;
}

导弹防御系统

• 迭代加深求最小值

#include <iostream>

using namespace std;

const int N = 55;

int a[N];
int uu[N];// 存储的是当前每个上升子序列的末尾值
int dd[N];// 存储的是当前每个下降子序列的末尾值
int n;

/*
    depth：上升子序列的个数和下降子序列的个数的总和的上限
    u：从下标为u开始，遍历a数组中的每个元素
    cntuu：上升子序列的个数
    cntdd：下降子序列的个数
*/
bool dfs(int depth, int u, int cntuu, int cntdd)
{
    // 当上升子序列的个数和下降子序列的个数的总和大于depth时，则需要继续进行迭代加深
    if (cntuu + cntdd > depth)
        return false;
        
    // 当u等于n时，表示已经遍历完a数组中的所有元素，即已经找到最优解，因为u是从0开始的
    if (u == n)
        return true;
        
    // 先判断把当前元素放到上升子序列的末尾
    bool flag = false;
    for (int i = 1; i <= cntuu; i++)// 找到第一个放到上升子序列的末尾的位置，即为最合适的位置
        if (a[u] > uu[i])
        {
            int t = uu[i];
            uu[i] = a[u];
            if (dfs(depth, u + 1, cntuu, cntdd))
                return true;
            uu[i] = t;// 状态还原，也称恢复现场
            flag = true;
            break;// 这里的break，就是优化，因为当前就是最合适的位置
        }
    if (!flag)// 如果没有找到能放到上升子序列的末尾的位置，则当前元素需要单独开辟一个上升子序列存放
    {
        uu[cntuu + 1] = a[u];
        if (dfs(depth, u + 1, cntuu + 1, cntdd))
            return true;
    }
    
    // 再判断把当前元素放到下降子序列的末尾
    flag = false;
    for (int i = 1; i <= cntdd; i++)// 找到第一个放到下降子序列的末尾的位置，即为最合适的位置
        if (a[u] < dd[i])
        {
            int t = dd[i];
            dd[i] = a[u];
            if (dfs(depth, u + 1, cntuu, cntdd))
                return true;
            dd[i] = t;// 状态还原，也称恢复现场
            flag = true;
            break;// 这里的break，就是优化，因为当前就是最合适的位置
        }
    if (!flag)// 如果没有找到能放到下降子序列的末尾的位置，则当前元素需要单独开辟一个下降子序列存放
    {
        dd[cntdd + 1] = a[u];
        if (dfs(depth, u + 1, cntuu, cntdd + 1))
            return true;
    }
    
    // 如果都不满足，即返回false
    return false;
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
            
        int depth = 0;// 存储的是上升子序列的个数和下降子序列的个数的总和的上限
        
        /*
            这个上限每次往上加1，
            直至在当前上限进行dfs时能找到最优解，
            这种dfs求最小值的方法被称为迭代加深求最小值
        */
        while (!dfs(depth, 0, 0, 0))
            depth++;
            
        printf("%d\n", depth);
    }
    
    return 0;
}

• 定义一个全局变量求最小值

#include <iostream>

using namespace std;

const int N = 55;

int a[N];
int uu[N];// 存储的是当前每个上升子序列的末尾值
int dd[N];// 存储的是当前每个下降子序列的末尾值
int n;
int ans;// 定义一个全局变量求最小值

/*
    u：从下标为u开始，遍历a数组中的每个元素
    cntuu：上升子序列的个数
    cntdd：下降子序列的个数
*/
void dfs(int u, int cntuu, int cntdd)
{
    /*
        当cntuu + cntdd >= ans成立时，
        表示ans已经不可能再变小了，则可以停止进行dfs，
        极大地提高效率。
        
        如果写成cntuu + cntdd > ans，
        则有可能会发生tle（超时）的情况，
        因为会把大量的cntuu + cntdd == ans成立时的情况也进行了dfs操作，
        效率会极大降低。
    */
    if (cntuu + cntdd >= ans)
        return;
        
    if (u == n)
    {
        // 因为ans是全局变量，结合上面的判断：cntuu + cntdd >= ans，能保证ans是一直在变小的
        ans = cntuu + cntdd;
        return;
    }
    
    // 先判断把当前元素放到上升子序列的末尾
    int k = 0;// 从第0个上升子序列开始遍历
    // 当没有遍历完上升子序列，并且当前上升子序列的末尾值大于等于当前元素，则需要继续遍历
    while (k < cntuu && uu[k] >= a[u])// 找到第一个放到上升子序列的末尾的位置，即为最合适的位置
        k++;
    int t = uu[k];
    uu[k] = a[u];
    if (k == cntuu)// 这是需要单独开辟一个上升子序列的情况
        dfs(u + 1, cntuu + 1, cntdd);
    else
        dfs(u + 1, cntuu, cntdd);
    uu[k] = t;// 状态还原，也称恢复现场
    
    // 再判断把当前元素放到下降子序列的末尾
    k = 0;// 从第0个下降子序列开始遍历
    // 当没有遍历完下降子序列，并且当前下降子序列的末尾值小于等于当前元素，则需要继续遍历
    while (k < cntdd && dd[k] <= a[u])// 找到第一个放到下降子序列的末尾的位置，即为最合适的位置
        k++;
    t = dd[k];
    dd[k] = a[u];
    if (k == cntdd)// 这是需要单独开辟一个下降子序列的情况
        dfs(u + 1, cntuu, cntdd + 1);
    else
        dfs(u + 1, cntuu, cntdd);
    dd[k] = t;// 状态还原，也称恢复现场
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
            
        ans = n;// 最坏情况下是n
        
        dfs(0, 0, 0);
        
        printf("%d\n", ans);
    }
    return 0;
}

最长公共上升子序列

• 状态表示：f[i,j]（f[i,j]表示，在，由，在第一个序列的前i个字母中出现且在第二个序列的前j个字母中出现且以b[j]结尾的每个公共上升子序列的长度，组成的集合，中，的最大值。其中，b[j]表示第二个序列的第j个字母）
• 状态计算：f[i,j]=max(f[i-1,j],f[i-1,k]+1)（其中，k∈{1,2,…,j-1}）

最长公共上升子序列

• 朴素版，会超时（tle）

#include <iostream>

using namespace std;

const int N = 3e3 + 10;

int a[N], b[N];
int f[N][N];// 状态表示

int main()
{
    int n;
    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++)
        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 (b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }
        
    int res = 0;
    for (int j = 1; j <= n; j++)
        res = max(res, f[n][j]);
        
    printf("%d\n", res);
    
    return 0;
}

• 改进版，会超时（tle）

#include <iostream>

using namespace std;

const int N = 3e3 + 10;

int a[N], b[N];
int f[N][N];// 状态表示

int main()
{
    int n;
    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++)
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j])
            {
                int maxv = 1;
                for (int k = 1; k < j; k++)
                    if (b[k] < b[j])
                        maxv = max(maxv, f[i - 1][k] + 1);
                f[i][j] = max(f[i][j], maxv);
            }
        }
        
    int res = 0;
    for (int j = 1; j <= n; j++)
        res = max(res, f[n][j]);
        
    printf("%d\n", res);
    
    return 0;
}

• 优化版，对代码作等价变形，直接降低时间复杂度

#include <iostream>

using namespace std;

const int N = 3e3 + 10;

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

int main()
{
    int n;
    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 = 1;
        
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            
            if (b[j] < a[i])
                maxv = max(maxv, f[i - 1][j] + 1);
                
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], maxv);
        }
    }
    
    int res = 0;
    for (int j = 1; j <= n; j++)
        res = max(res, f[n][j]);
        
    printf("%d\n", res);
    
    return 0;
}

背包模型

完全背包问题，观察下面的状态计算（虽然每件物品有无限个，但是背包容量是有限的）：

f[i,j]=max(f[i-1,j],f[i-1,j-1*vi]+1*wi, f[i-1,j-2*vi]+2*wi, f[i-1,j-3*vi]+3*wi, ..., f[i-1,j-s*vi]+s*wi)
    
f[i,j-vi]=max(		f[i-1,j-1*vi]     , f[i-1,j-2*vi]+1*wi, f[i-1,j-3*vi]+2*wi, ..., f[i-1,j-s*vi]+(s-1)*wi)
    
f[i,j-2*vi]=max(	                    f[i-1,j-2*vi]     , f[i-1,j-3*vi]+1*wi, ..., f[i-1,j-s*vi]+(s-2)*wi)

f[i,j-3*vi]=max(	                    				  , f[i-1,j-3*vi]	  , ..., f[i-1,j-s*vi]+(s-3)*wi)
    
...
...
...

f[i,j-s*vi]=max(	                    				    				         f[i-1,j-s*vi]         )

多重背包问题，观察下面的状态计算（假设背包容量足够大，大到可以装下每件物品的上限个数）：

f[i,j]=max(f[i-1,j],f[i-1,j-1*vi]+1*wi, f[i-1,j-2*vi]+2*wi, f[i-1,j-3*vi]+3*wi, ..., f[i-1,j-s*vi]+s*wi)
    
f[i,j-vi]=max(		f[i-1,j-1*vi]     , f[i-1,j-2*vi]+1*wi, f[i-1,j-3*vi]+2*wi, ..., f[i-1,j-(s+1)*vi]+s*wi)
    
f[i,j-2*vi]=max(	                    f[i-1,j-2*vi]     , f[i-1,j-3*vi]+1*wi, ..., f[i-1,j-(s+2)*vi]+s*wi)
    
f[i,j-3*vi]=max(	                                        f[i-1,j-3*vi]     , ..., f[i-1,j-(s+3)*vi]+s*wi)

...
...
...
    
f[i,j-s*vi]=max(	                                        						 f[i-1,j-s*vi]	       , ..., f[i-1,j-(s+s)*vi]+s*wi)

...
...
...
    
以次类推，总会达到背包的容量上限，直至无法装下一个某件物品，然后结束

多重背包问题，观察下面的状态计算（假设背包容量足够大，大到可以装下每件物品的上限个数），有助于解题（多重背包问题 III）：

f[i,r]		=max(f[i-1,r])

f[i,r+v]	=max(f[i-1,r]+w	 , f[i-1,r+v])
    
f[i,r+2*v]	=max(f[i-1,r]+2*w, f[i-1,r+v]+1*w    , f[i-1,r+2*v])
    
f[i,r+3*v]  =max(f[i-1,r]+3*w, f[i-1,r+v]+2*w	 , f[i-1,r+2*v]+1*w, 	 f[i-1,r+3*v])
    
...
...
...

f[i,r+s*v]	=max(f[i-1,r]+s*w, f[i-1,r+v]+(s-1)*w, f[i-1,r+2*v]+(s-2)*w, f[i-1,r+3*v]+(s-3)*w, ...)

...
...
...

以次类推，总会达到背包的容量上限，然后结束

多重背包问题 III

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中选并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值。f[N,V]即为最终的结果）
• 状态计算：f[i,j]=max(f[i-1,j-k*vi]+k*wi)（vi表示第i件物品的体积，wi表示第i件物品的价值，k表示第i件物品使用了k次）

多重背包问题 III

#include <iostream>
#include <cstring>

using namespace std;

const int V = 2e4 + 10;

int f[V];// 当前层的状态表示
int g[V];// 存储上一层的状态表示
int q[V];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是g数组的下标

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        
        memcpy(g, f, sizeof f);// 存储上一层的状态表示
        
        // 按照余数分类（mod v）
        for (int j = 0; j < v; j++)
        {
            // 一开始设定，队头为0，队尾为-1
            int hh = 0, tt = -1;
            
            // 当前层中的状态只会从上一层中余数相等（mod v）的状态转移过来    
            for (int k = j; k <= m; k += v)
            {
                // 判断队头对应的g数组的下标是否已经超出窗口的范围
                // 对于前层中的任意一个状态，在容量允许的条件下，我们会向前数s个
                // 注意，滑动窗口的长度为s+1，不是s
                if (hh <= tt && q[hh] < k - s * v)
                    hh++;

                /*
                    为了让滑动窗口在滑动的过程中，
                    同一下标所对应的状态值保持不变（因为这样才能进行比较，才能使用单调队列求滑动窗口中的最大值），
                    经过发现，我们可以把滑动窗口中的每个状态相对于余数j来说，加了多少个v，就减去几个w即可！！！
                    
                    当队列不为空，
                    且队尾对应的g数组的下标的状态的值（值为：g[q[tt]]-(q[tt]-j)/v*w）小于等于当前遍历到的状态的值（值为：g[k]-(k-j)/v*w），
                    则弹出队尾元素，保证队列的单调性
                */
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                    tt--;
                q[++tt] = k;// 这里的q数组记录的值是g数组的下标
                
                /*
                    经过发现，当前层的当前状态f[k]的值为g数组当前滑动窗口中的最大值，
                    即g[q[hh]]+(k-q[hh])/v*w
                */
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    
    // 输出结果
    printf("%d\n", f[m]);
    
    return 0;
}

采药

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中选并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值。f[N,V]即为最终的结果）
• 状态计算：f[i,j]=max(f[i-1,j],f[i-1,j-vi]+wi)（vi表示第i件物品的体积，wi表示第i件物品的价值）

采药

#include <iostream>

using namespace std;

const int T = 1e3 + 10;

int f[T];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        for (int j = m; j >= a; j--)
            f[j] = max(f[j], f[j - a] + b);
    }
    printf("%d\n", f[m]);
    return 0;
}

装箱问题

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中选并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值。f[N,V]即为最终的结果）
• 状态计算：f[i,j]=max(f[i-1,j],f[i-1,j-vi]+wi)（vi表示第i件物品的体积，wi表示第i件物品的价值）

装箱问题

#include <iostream>

using namespace std;

const int V = 2e4 + 10;

int f[V];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        for (int j = m; j >= a; j--)
            if (f[j - a] + a <= m)
                f[j] = max(f[j], f[j - a] + a);
    }
    printf("%d\n", m - f[m]);
    return 0;
}

宠物小精灵之收服

• 状态表示：f[i,j,k]（f[i,j,k]表示，在，由，只从前i个小精灵中选并且精灵球总消耗数小于等于j并且皮卡丘被消耗的总体力值小于k的每种选法的收服小精灵的总数，组成的集合，中，的最大值）
• 状态计算：f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+1)（v1[i]表示收服第i个小精灵需消耗的精灵球数，v2[i]表示收服第i个小精灵需消耗的皮卡丘的体力值）

宠物小精灵之收服

#include <iostream>

using namespace std;

const int N = 100 + 10;
const int V1 = 1e3 + 10;
const int V2 = 500 + 10;

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int f[V1][V2];

int main()
{
    int v1, v2, n;
    scanf("%d %d %d", &v1, &v2, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        for (int j = v1; j >= a; j--)
            for (int k = v2 - 1; k >= b; k--)
                f[j][k] = max(f[j][k], f[j - a][k - b] + 1);
    }
    
    // 输出收服的精灵个数的最大值
    printf("%d ", f[v1][v2 - 1]);
    
    // 在收服的精灵个数最多的情况下，令皮卡丘受到的伤害最小
    for (int i = 0; i <= v2 - 1; i++)
        if (f[v1][i] == f[v1][v2 - 1])
        {
            // 输出皮卡丘的剩余体力
            printf("%d\n", v2 - i);
            break;
        }
        
    return 0;
}

二维费用的背包问题

• 状态表示：f[i,j,k]（f[i,j,k]表示，在，由，只从前i件物品中选并且总体积小于等于j并且总重量小于等于k的每种选法的总价值，组成的集合，中，的最大值）
• 状态计算：f[i,j,k]=max(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+w[i])（v1[i]表示第i件物品的体积，v2[i]表示第i件物品的重量，w[i]表示第i件物品的价值）

二维费用的背包问题

#include <iostream>

using namespace std;

const int N = 1e3 + 10;
const int V1 = 100 + 10;
const int V2 = 100 + 10;

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int f[V1][V2];

int main()
{
    int n, v1, v2;
    scanf("%d %d %d", &n, &v1, &v2);
    
    for (int i = 1; i <= n; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        for (int j = v1; j >= a; j--)
            for (int k = v2; k >= b; k--)
                f[j][k] = max(f[j][k], f[j - a][k - b] + w);
    }
    
    printf("%d\n", f[v1][v2]);
    
    return 0;
}

数字组合

• 状态表示：f[i,j]（f[i,j]表示，只从前i件物品中选并且总体积恰好等于j，的组合数）
• 状态计算：f[i,j]=f[i-1,j]+f[i-1,j-vi]（vi表示第i件物品的体积）

数字组合

#include <iostream>

using namespace std;

const int M = 1e4 + 10;

int f[M];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 根据状态表示可得，f[0][0]=1
    f[0] = 1;
    
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = m; j >= x; j--)
            f[j] = f[j] + f[j - x];
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

庆功会

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中选并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值。f[N,V]即为最终的结果）
• 状态计算：f[i,j]=max(f[i-1,j-k*vi]+k*wi)（vi表示第i件物品的体积，wi表示第i件物品的价值，k表示第i件物品使用了k次）

庆功会

#include <iostream>

using namespace std;

const int N = 500 + 10;
const int M = 6e3 + 10;

int f[M];

// 一维数组优化多重背包问题
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        for (int j = m; j >= 1; j--)
            for (int k = 0; k <= s && k * v <= j; k++)
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    printf("%d\n", f[m]);
    return 0;
}

买书

• 状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
• 状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+…（vi表示第i件物品的体积）

买书

#include <iostream>

using namespace std;

const int N = 10;
const int M = 1e3 + 10;

int v[N];
int f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和4件物品，每件物品的体积为10,20,50,100，每件物品可以使用无限次。
		求解从第1~4件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    v[1] = 10, v[2] = 20, v[3] = 50, v[4] = 100;
    
    int m;
    scanf("%d", &m);
    
    // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
    f[0] = 1;
    
    // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
    // 状态计算的过程可以用一维数组去优化
    for (int i = 1; i <= 4; i++)
        /*
            这里用到了滚动数组的核心思想：
                用上一层的旧数据算出新数据，
                然后用新数据覆盖当前层的旧数据，
                以此类推再继续计算
                （上一层和当前层对应的是同一层下的两种不同状态）
        */
        // 第i件物品的体积为vi
        for (int j = v[i]; j <= m; j++)
            f[j] = f[j] + f[j - v[i]];
            
    printf("%d\n", f[m]);
    
    return 0;
}

潜水员

• 状态表示：f[i,j,k]（f[i,j,k]表示，在，由，只从前i件物品中选并且总体积至少等于j并且总重量至少等于k的每种选法的总价值，组成的集合，中，的最小值）
• 状态计算：f[i,j,k]=min(f[i-1,j,k],f[i-1,j-v1[i],k-v2[i]]+w[i])（v1[i]表示第i件物品的体积，v2[i]表示第i件物品的重量，w[i]表示第i件物品的价值）

潜水员

#include <iostream>
#include <cstring>

using namespace std;

const int V1 = 22;
const int V2 = 80;

int f[V1][V2];

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int main()
{
    int v1, v2, n;
    scanf("%d %d %d", &v1, &v2, &n);
    
    memset(f, 0x3f, sizeof f);// 把无意义的状态赋值为0x3f3f3f3f
    f[0][0] = 0;// 根据状态表示可得，f[0][0]=0
    
    for (int i = 1; i <= n; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        
        // 状态计算
        for (int j = v1; j >= 0; j--)
            for (int k = v2; k >= 0; k--)
                // 当j-a、k-b的值为负数时，则视为从0转移过来
                f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + w);
    }
    
    printf("%d\n", f[v1][v2]);
    
    return 0;
}

背包问题求具体方案

#include <iostream>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;

int f[N][M];
int v[N];
int w[N];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &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]);
        }
        
    // 此时，f[1][m]存的就是总价值最大的结果
        
    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])
        {
            printf("%d ", i);
            j -= v[i];
        }
    
    return 0;
}

机器分配

#include <iostream>

using namespace std;

const int N = 15;
const int M = 20;

int f[N][M];
int v[N][M];
int w[N][M];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= m; k++)
        {
            v[i][k] = k;
            scanf("%d", &w[i][k]);
        }
        
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= m; k++)
                if (j >= v[i][k])
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
        
    printf("%d\n", f[n][m]);
    
    // 此时，f[n][m]存的就是总价值最大的结果
    
    int j = m;
    // 从结果往前推，输出任意合法方案即可
    for (int i = n; i >= 1; i--)
        for (int k = m; k >= 0; k--)
            if (j >= v[i][k] && f[i][j] == f[i - 1][j - v[i][k]] + w[i][k])
            {
                printf("%d %d\n", i, k);
                j -= k;
                break;
            }
            
    return 0;
}

金明的预算方案

#include <iostream>
#include <vector>

using namespace std;

const int N = 65;
const int M = 32010;

pair<int, int> master[N];// 存储主件物品的信息
vector<pair<int, int>> annex[N];// 存储附件物品的信息，和其对应的主件物品关联
int f[M];

// 一维数组优化分组背包问题
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if (!q)
            master[i] = {v, v * p};
        else
            annex[q].push_back({v, v * p});
    }
    
    for (int i = 1; i <= n; i++)
        // 选附件物品时，必须要选上其对应的主件物品
        if (master[i].first)
            for (int j = m; j >= 0; j--)
                // 枚举每个主件物品和其对应的附件物品选取的所有方案
                for (int k = 0; k < 1 << annex[i].size(); k++)
                {
                    // 每个方案都包含主件物品
                    int v = master[i].first;
                    int w = master[i].second;
                    
                    for (int u = 0; u < annex[i].size(); u++)
                        // 判断当前这个方案附件物品选取的情况
                        if (k >> u & 1)
                        {
                            v += annex[i][u].first;
                            w += annex[i][u].second;
                        }
                        
                    if (j >= v)
                        f[j] = max(f[j], f[j - v] + w);
                }
                
    printf("%d\n", f[m]);
    
    return 0;
}

开心的金明

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中选并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值。f[N,V]即为最终的结果）
• 状态计算：f[i,j]=max(f[i-1,j],f[i-1,j-vi]+wi)（vi表示第i件物品的体积，wi表示第i件物品的价值）

开心的金明

#include <iostream>

using namespace std;

const int N = 30;
const int M = 3e4 + 10;

int f[M];

// 一维数组优化01背包问题
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int v, p;
        scanf("%d %d", &v, &p);
        for (int j = m ; j >= 0; j--)
            if (j >= v)
                f[j] = max(f[j], f[j - v] + v * p);
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

货币系统

#include <iostream>

using namespace std;

const int N = 20;
const int M = 3e3 + 10;

long long f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和n件物品，每件物品的体积为v1,v2,v3,...,vi,...,vn，每件物品可以使用无限次。
		求解从第1~n件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
    f[0] = 1;
    
    // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
    // 状态计算的过程可以用一维数组去优化
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = x; j <= m; j++)
            f[j] = f[j] + f[j - x];
    }
    
    printf("%lld\n", f[m]);
    
    return 0;
}

货币系统

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

using namespace std;

const int N = 110;
const int M = 25010;

int a[N];
int f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和n件物品，每件物品的体积为v1,v2,v3,...,vi,...,vn，每件物品可以使用无限次。
		求解从第1~n件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        
        // 把货币按货币面额的值从小到大进行排序，因为货币面额大的货币可以由货币面额小的货币表示出来
        sort(a + 1, a + 1 + n);
        
        memset(f, 0, sizeof f);
        // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
        f[0] = 1;
        
        int res = n;// 存储当前货币系统可以简化为多少个货币
        
        // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
        // 状态计算的过程可以用一维数组去优化
        for (int i = 1; i <= n; i++)
        {
            for (int j = a[i]; j <= a[n]; j++)
                f[j] = f[j] + f[j - a[i]];
                
            // 货币面额大的货币可以由货币面额小的货币表示出来
            /*
                当此货币面额的货币除了能被其本身表示，还能由货币面额小的货币表示出来，
                则此货币面额的货币没有存在的必要，意味着这套货币系统可以进行简化
            */
            if (f[a[i]] > 1)
                res--;
        }
        
        printf("%d\n", res);
    }
    return 0;
}

混合背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;

int f[M];// 当前层的状态表示
int g[M];// 存储上一层的状态表示
int q[M];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是g数组的下标

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        
        if (s == -1)// 01背包问题
        {
            for (int j = m; j >= v; j--)
                f[j] = max(f[j], f[j - v] + w);
        }
        else if (s == 0)// 完全背包问题
        {
            for (int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else// 单调队列优化多重背包问题
        {
            // 按照余数分类（mod v）
            for (int j = 0; j < v; j++)
            {
                // 一开始设定，队头为0，队尾为-1
                int hh = 0, tt = -1;
                
                // 当前层中的状态只会从上一层中余数相等（mod v）的状态转移过来
                for (int k = j; k <= m; k += v)
                {
                    // 判断队头对应的g数组的下标是否已经超出窗口的范围
                    // 对于前层中的任意一个状态，在容量允许的条件下，我们会向前数s个
                    // 注意，滑动窗口的长度为s+1，不是s
                    if (hh <= tt && q[hh] < k - s * v)
                        hh++;
                        
                    /*
                        为了让滑动窗口在滑动的过程中，
                        同一下标所对应的状态值保持不变（因为这样才能进行比较，才能使用单调队列求滑动窗口中的最大值），
                        经过发现，我们可以把滑动窗口中的每个状态相对于余数j来说，加了多少个v，就减去几个w即可！！！
                        
                        当队列不为空，
                        且队尾对应的g数组的下标的状态的值（值为：g[q[tt]]-(q[tt]-j)/v*w）小于等于当前遍历到的状态的值（值为：g[k]-(k-j)/v*w），
                        则弹出队尾元素，保证队列的单调性
                    */
                    while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                        tt--;
                    q[++tt] = k;// 这里的q数组记录的值是g数组的下标
                    
                    /*
                        经过发现，当前层的当前状态f[k]的值为g数组当前滑动窗口中的最大值，
                        即g[q[hh]]+(k-q[hh])/v*w
                    */
                    f[k] = g[q[hh]] + (k - q[hh]) / v * w;
                }
            }
        }
        
        memcpy(g, f, sizeof f);// 存储上一层的状态表示
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

有依赖的背包问题

• 状态表示
  • f[u,j]（f[u,j]表示，在，由，从以u结点为根结点的子树中选择并且选择根结点并且总体积小于等于j的每种选法的总价值，组成的集合，中，的最大值）
• 状态计算
  • 要结合树形DP和分组背包问题进行分析

有依赖的背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
const int V = 110;
const int M = 110;

int v[N], w[N];

int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条边

int f[N][V];// 状态表示
int n, volume;

void add(int a, int b)// 插入一条a节点指向b节点的边
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    /*
        先把当前子树中的根节点（即u节点）排除掉，因此要先把u节点的体积去掉
        
        然后可以把若干个子节点看成若干组物品，
        每组物品中根据给当前子节点分配的不同的体积对应有不同的物品，即可视为每组物品中有若干件物品，
        每件物品可能有不同的价值（因为给当前子节点分配的不同的体积，可能会对应得到不同的价值），
        每一组物品中最多只能选一件物品（因为每个子节点只能选一次）
        
        此时的思路可以用分组背包问题去考虑，
        结合分组背包问题的状态表示去理解，
        实际操作和用一维数组去优化分组背包问题的解题过程相似，
        此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组
    */
    
    /*
        此时的思路可以用分组背包问题去考虑，
        结合分组背包问题的状态表示去理解，
        实际操作和用一维数组去优化分组背包问题的解题过程相似，
        此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组
    */
    for (int i = h[u]; i != -1; i = ne[i])// 依次遍历每组物品（循环物品组）
    {
        // 要结合树形DP进行分析，所以要先进行递归操作
        dfs(e[i]);
        
        for (int j = volume - v[u]; j >= 0; j--)// 先把u节点的体积去掉，然后体积从大到小循环（循环体积）
            /*
                每组物品中根据给当前子节点分配的不同的体积对应有不同的物品，即可视为每组物品中有若干件物品，
                每件物品可能有不同的价值（因为给当前子节点分配的不同的体积，可能会对应得到不同的价值），
                每一组物品中最多只能选一件物品（因为每个子节点只能选一次）
            */
            for (int k = 1; k <= j; k++)// 遍历给当前子节点分配的体积（循环决策）
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);// 注意，通过dfs操作回溯后，这里的f[e[i]][k]是本题目状态表示的含义
    }
    
    // 到这里为止，f[u][j]并不是本题目状态表示的含义，因为还没有把当前子树中的根节点（即u节点）选上
    
    // 按照本题目状态表示的含义，要把当前子树中的根节点（即u节点）也选上
    for (int j = volume; j >= v[u]; j--)// 注意，这里一定要从大到小循环
        f[u][j] = f[u][j - v[u]] + w[u];
    // 体积不够，则无法选择当前子树中的根节点（即u节点）
    for (int j = 0; j < v[u]; j++) 
        f[u][j] = 0;// 即为0
}

int main()
{
    scanf("%d %d", &n, &volume);
    
    // 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连
    memset(h, -1, sizeof h);
    
    int root;
    for (int i = 1; i <= n; i++)
    {
        int p;
        scanf("%d %d %d", &v[i], &w[i], &p);
        
        if (p == -1)
            root = i;
        else
            add(p, i);
    }
    
    // 从根结点开始进行，状态计算
    dfs(root);
    
    // 输出结果
    printf("%d\n", f[root][volume]);
    
    return 0;
}

背包问题求方案数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;
const int MOD = 1e9 + 7;

/*
    f[i][j]的二维状态表示：f[i,j]表示，在，由，只从前i件物品中选并且总体积恰好等于j的每种选法的总价值，组成的集合，中，的最大值
    g[i][j]的二维状态表示：g[i,j]表示，在f[i,j]取到最大值时，的方案数
*/
int f[M];// 一维优化
int g[M];// 一维优化

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);// 这一步很有必要，因为要结合f[i][j]的二维状态表示的含义去理解
    f[0] = 0;
    // 根据状态表示可得
    g[0] = 1;
    
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        scanf("%d %d", &v, &w);
        
        for (int j = m; j >= v; j--)
        {
            int maxv = max(f[j], f[j - v] + w);
            
            int cnt = 0;// 记录当前情况下的方案数
            if (maxv == f[j])
                // 如果是不选择当前第i个物品时取到最大值，当前情况下的方案数要加上这种情况下的方案数
                cnt += g[j];
            if (maxv == f[j - v] + w)
                // 如果是选择当前第i个物品时取到最大值，当前情况下的方案数要加上这种情况下的方案数
                cnt += g[j - v];
                
            g[j] = cnt % MOD;
            
            f[j] = maxv;
        }
    }
    
    // 找到最优选法（即总价值最大）
    int t = 0;
    for (int j = 0; j <= m; j++)
        t = max(t, f[j]);
        
    // 最优选法（即总价值最大）的方案数
    int sum = 0;
    for (int j = 0; j <= m; j++)
        if (t == f[j])
            sum = (sum + g[j]) % MOD;
        
    // 输出最优选法（即总价值最大）的方案数
    printf("%d\n", sum);
    
    return 0;
}

能量石

• 状态表示：f[i,j]（f[i,j]表示，在，由，只从前i件物品中吃并且总耗时恰好等于j的每种选法的总能量，组成的集合，中，的最大值）
• 状态计算：f[i,j]=max(f[i-1,j],f[i-1,j-Si]+Ei-(j-Si)*Li)（Si表示吃完第i件物品需要花费的时间，Ei表示第i件物品最初包含Ei单位的能量，Li表示第i件物品每秒将失去Li单位的能量）

能量石

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

using namespace std;

const int N = 100 + 10;
const int M = 1e4 + 10;

int f[M];// 一维数组优化

struct Stone
{
    int s, e, l;
    bool operator< (const Stone& t) const
    {
        /*
            经过分析，按每个能量石的s/l的值从小到大进行排序，依次考虑，
            是最优策略，可以得到最优解
            
            注意：
                不要写成除法形式（因为分母可能为0）：s / l < t.s / t.l
                要写成乘法形式：s * t.l < t.s * l
        */
        return s * t.l < t.s * l;
    }
}stone[N];

int main()
{
    int t;
    scanf("%d", &t);
    
    for (int c = 1; c <= t; c++)
    {
        int n;
        scanf("%d", &n);
        
        int m = 0;
        
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d %d", &stone[i].s, &stone[i].e, &stone[i].l);
            m += stone[i].s;
        }
        
        // 按每个能量石的s/l的值从小到大进行排序
        sort(stone, stone + n);
        
        // 根据状态表示可得
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        
        for (int i = 0; i < n; i++)
            for (int j = m; j >= stone[i].s; j--)
                // 状态计算
                f[j] = max(f[j], f[j - stone[i].s] + stone[i].e - (j - stone[i].s) * stone[i].l);
                
        int res = 0;
        for (int j = 0; j <= m; j++)
            res = max(res, f[j]);
            
        printf("Case #%d: %d\n", c, res);
    }
    
    return 0;
}

状态机模型

状态机：当一个DP问题的状态不好表示的时候，我们可以考虑用状态机的形式把这个不好表示的状态分离开，然后表示出来

大盗阿福

• 状态表示：f[i,j]（f[i,j]表示，在，由，从状态机中走了i步且当前位于状态j的每种走法的总现金，组成的集合，中，的最大值。其中，每走一步对应一家店铺，j∈{0,1}，0表示未选最后一个店铺的状态，1表示选了最后一个店铺的状态）
• 状态计算：
  • f[i,0]=max(f[i-1,0],f[i-1,1])
  • f[i,1]=f[i-1,0]+w[i]（wi表示第i家店铺的现金）

大盗阿福

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int f[N][2];// 状态表示
int w[N];

int main()
{
    int t;
    scanf("%d", &t);
    
    while (t--)
    {
        int n;
        scanf("%d", &n);
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
            
        // 根据状态表示可得
        f[0][0] = 0;
        f[0][1] = -0x3f3f3f3f;
        
        // 状态计算
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }
        
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    
    return 0;
}

股票买卖 IV

• 状态表示：f[i,j,k]（f[i,j,k]表示，在，由，从状态机中走了i步且当前已经进行过j次交易且当前位于状态k的每种走法的总利润，组成的集合，中，的最大值。其中，每走一步对应一天股价，k∈{0,1}，0表示手中无货的状态，1表示手中有货的状态）
• 状态计算：
  • f[i,j,0]=max(f[i-1,j,0],f[i-1,j,1]+w[i])（wi表示第i天的股价）
  • f[i,j,1]=max(f[i-1,j,1],f[i-1,j-1,0]-w[i])（wi表示第i天的股价）

股票买卖 IV

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 100 + 10;

int f[N][M][2];// 状态表示
int w[N];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
        
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);
    // 根据状态表示可得
    for (int i = 0; i <= n; i++)
        f[i][0][0] = 0;
        
    // 状态计算
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
        
    int res = 0;
    for (int j = 0; j <= m; j++)
        res = max(res, f[n][j][0]);
        
    printf("%d\n", res);
    
    return 0;
}

股票买卖 V

• 状态表示：f[i,j]（f[i,j]表示，在，由，从状态机中走了i步且当前位于状态j的每种走法的总利润，组成的集合，中，的最大值。其中，每走一步对应一天股价，j∈{0,1,2}，0表示手中有货的状态，1表示手中无货一天的状态，2表示手中无货大于等于两天的状态）
• 状态计算：
  • f[i,0]=max(f[i-1,0],f[i-1,2]-w[i])（wi表示第i天的股价）
  • f[i,1]=f[i-1,0]+w[i]（wi表示第i天的股价）
  • f[i,2]=max(f[i-1,1],f[i-1,2])（wi表示第i天的股价）

股票买卖 V

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int f[N][3];// 状态表示
int w[N];

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
        
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);
    f[0][2] = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }
    
    // 极端情况：股票一直在跌，此时最大利润为0
    printf("%d\n", max(f[n][1], f[n][2]));
    
    return 0;
}

设计密码

• 状态表示：f[i,j]（f[i,j]表示，从状态机中走了i步，且当前位于状态j，的组合数。其中，每走一步对应字符串中的一个字符，j∈{0,1,2,…,m}，0表示模式串下标为0的状态，1表示模式串下标为1的状态，2表示模式串下标为2的状态，…，m表示模式串下标为m的状态）
• 状态计算：f[i+1,u]=f[i+1,u]+f[i,j]

设计密码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50 + 10;
const int M = 50 + 10;
const int MOD = 1e9 + 7;

int n;
char str[M];// 模式串
int ne[M];// 模式串的next数组
int f[N][M];// 状态表示

int main()
{
    scanf("%d", &n);
    scanf("%s", str + 1);// 从下标为1开始读入
    
    int m = strlen(str + 1);// 注意，这里要从下标为1开始计算模式串的长度
    
    // 求模式串的next数组的过程
    // i从2开始，是因为ne[1]=0，相当于规定了模式串相等部分的前缀和后缀的长度不能相同
    for (int i = 2, j = 0; i <= m; i++)
    {
        while (j && str[j + 1] != str[i]) 
            j = ne[j];
            
        if (str[j + 1] == str[i]) 
            j++;
            
        ne[i] = j;// 记录next数组的值
    }
    
    // 根据状态表示可得
    f[0][0] = 1;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 'a'; k <= 'z'; k++)
            {
                int u = j;
                
                while (u && str[u + 1] != k)
                    u = ne[u];
                    
                if (str[u + 1] == k)
                    u++;
                    
                if (u < m)// 当u==m时，则没有必要进行状态计算，因为不符合题意
                    // 状态计算
                    f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }
            
    int res = 0;
    // 根据状态表示可得
    for (int j = 0; j < m; j++)
        res = (res + f[n][j]) % MOD;
        
    printf("%d\n", res);
    
    return 0;
}

状态压缩DP

状态压缩DP

• 棋盘式
• 集合式

小国王

• 状态表示：f[i,k,s]（f[i,k,s]表示，只摆放在前i行且已经摆放了k个国王且第i行摆放的状态是s，的组合数）

  举个例子：假设存在5行5列的棋盘，f[3,7,26]表示，只摆放在前3行且已经摆放了7个国王且第3行摆放的列为第1列、第2列、第4列，二进制表示为11010，十进制表示为26，的组合数

• 状态计算：f[i,k,s]=sum(f[i-1,k-count(s),t])（其中，count(s)表示二进制表示中的s的1的个数，s、t∈{0,1,2,3,…,2^(棋盘的列数)-1}，并且s、t需要满足以下条件：1、二进制表示中的s、t不存在连续两个1的情况；2、s&t（位运算）的结果要等于0；3、s|t（位运算）的结果不存在连续两个1的情况）

小国王

#include <iostream>
#include <vector>

using namespace std;

const int N = 10 + 2;
const int K = 100 + 10;
const int S = 1 << 10;

typedef long long LL;

int n, k;
vector<int> state;// 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
int cnt[S];
vector<int> head[S];// 存储两个合法的状态间的合法状态转移
LL f[N][K][S];// 状态表示

// 判断二进制表示中的状态是否存在连续两个1的情况
bool check(int state)
{
    return !(state & (state >> 1));
}

// 计算二进制表示中的状态的1的个数
int count(int state)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (state >> i & 1)
            sum++;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &k);
    
    for (int i = 0; i < 1 << n; i++)
        if (check(i))
        {
            // 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
            state.push_back(i);
            
            // 存储二进制表示中的i的1的个数
            cnt[i] = count(i);
        }
        
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            
            /*
                两个合法的状态间的合法状态转移，要满足以下条件：
                    1、a&b（位运算）的结果要等于0
                    2、a|b（位运算）的结果不存在连续两个1的情况
            */
            if ((a & b) == 0 && check(a | b))
                head[a].push_back(b);
        }
    
    // 根据状态表示可得    
    f[0][0][0] = 1;
    
    // 状态计算
    for (int i = 1; i <= n + 1; i++)// 这里计算到n+1，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j <= k; j++)
            for (int x = 0; x < state.size(); x++)
                for (int t : head[state[x]])
                {
                    int temp = cnt[state[x]];
                    if (j >= temp)
                        f[i][j][state[x]] += f[i - 1][j - temp][t];
                }
    
    // 根据状态表示，直接输出结果            
    printf("%lld\n", f[n + 1][k][0]);
    
    return 0;
}

玉米田

• 状态表示：f[i,s]（f[i,s]表示，只摆放在前i行且第i行摆放的状态是s，的组合数）

  举个例子：假设存在5行5列的玉米地，f[3,26]表示，只摆放在前3行且第3行摆放的列为第1列、第2列、第4列，二进制表示为11010，十进制表示为26，的组合数

• 状态计算：f[i,s]=sum(f[i-1,t])（其中，s、t∈{0,1,2,3,…,2^(玉米地的列数)-1}，并且s、t需要满足以下条件：1、二进制表示中的s、t不存在连续两个1的情况；2、摆放的状态s、t不能存在摆放在不育的玉米地上的情况；3、s&t（位运算）的结果要等于0）

玉米田

#include <iostream>
#include <vector>

using namespace std;

const int N = 14;
const int M = 12;
const int S = 1 << M;
const int MOD = 1e8;

int n, m;
int g[N];// 存储玉米地的情况
vector<int> state;// 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
vector<int> head[S];// 存储两个合法的状态间的合法状态转移
int f[N][S];// 状态表示

// 判断二进制表示中的状态是否存在连续两个1的情况
bool check(int state)
{
    return !(state & (state >> 1));
}

int main()
{
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int j = m - 1; j >= 0; j--)
        {
            int t;
            scanf("%d", &t);
            
            // 存储玉米地的情况
            g[i] = g[i] + (!t << j);
        }
        
    for (int i = 0; i < 1 << m; i++)
        if (check(i))
            // 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
            state.push_back(i);
            
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            
            /*
                两个合法的状态间的合法状态转移，要满足以下条件：
                    1、a&b（位运算）的结果要等于0
            */
            if ((a & b) == 0)
                head[a].push_back(b);
        }
        
    // 根据状态表示可得 
    f[0][0] = 1;
    
    // 状态计算
    for (int i = 1; i <= n + 1; i++)// 这里计算到n+1，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j < state.size(); j++)
        {
            // 摆放的状态state[j]不能存在摆放在不育的玉米地上的情况
            if (state[j] & g[i])
                continue;
            
            for (int t : head[state[j]])
            {
                // 摆放的状态t不能存在摆放在不育的玉米地上的情况
                if (t & g[i - 1])
                    continue;
                    
                f[i][state[j]] = (f[i][state[j]] + f[i - 1][t]) % MOD;
            }
        }
        
    // 根据状态表示，直接输出结果
    printf("%d\n", f[n + 1][0]);
    
    return 0;
}

炮兵阵地

• 状态表示：f[i,j,k]（f[i,j,k]表示，在，由，只摆放在前i行且第i-1行摆放的状态是j且第i行摆放的状态是k的每种摆法的总数量，组成的集合，中，的最大值）

  举个例子：假设存在5行5列的网格地图，f[3,7,26]表示，在，由，只摆放在前3行且第2行摆放的列为第3列、第4列、第5列，二进制表示为00111，十进制表示为7，且第3行摆放的列为第1列、第2列、第4列，二进制表示为11010，十进制表示为26，的每种摆法的总数量，组成的集合，中，的最大值

• 状态计算：f[i,j,k]=max(f[i-1,s,j]+count(k))（其中，s为第i-2行摆放的状态，count(k)表示二进制表示中的k的1的个数，s、j、k∈{0,1,2,3,…,2^(网格地图的列数)-1}，并且s、j、k需要满足以下条件：1、二进制表示中的s、j、k不存在连续三位中包含两个1及以上的情况；2、摆放的状态s、j、k不能存在摆放在无法摆放的位置上的情况；3、s&j、s&k、j&k（位运算）的结果要等于0）

炮兵阵地

#include <iostream>
#include <vector>

using namespace std;

const int N = 103;
const int M = 10;
const int S = 1 << M;

int n, m;
int g[N];// 存储网格地图的情况
vector<int> state;// 存储所有，二进制表示中的状态不存在连续三位中包含两个1及以上的情况，的状态
int cnt[S];
/*
    因为这道题目有空间限制，
    所以需要用滚动数组来进行优化处理，
    把第一维设为2即可
*/
int f[2][S][S];// 状态表示

// 判断二进制表示中的状态是否存在连续三位中包含两个1及以上的情况
bool check(int state)
{
    for (int i = 0; i < m; i++)
        /*
	        运算符的优先级：算术运算符 > 移位运算符 > 位运算符 > 逻辑运算符
            如果实在记不住运算符的优先级，那就加括号处理
        */
        if ((state >> i & 1) & (state >> i + 1 & 1) || (state >> i & 1) & (state >> i + 2 & 1))
            return false;

    return true;
}

// 计算二进制表示中的状态的1的个数
int sum(int state)
{
    int res = 0;
    for (int i = 0; i < m; i++)
        if (state >> i & 1)
            res++;
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int j = m - 1; j >= 0; j--)
        {
            char t;
            cin >> t;// cin在输入时能够帮我们过滤空格，scanf则不行，它会读入空格。如果这里使用scanf则会有问题
            
            // 存储网格地图的情况
            if (t == 'H')
                g[i] = g[i] + (1 << j);
        }
        
    for (int i = 0; i < 1 << m; i++)
        if (check(i))
        {
            // 存储所有，二进制表示中的状态不存在连续三位中包含两个1及以上的情况，的状态
            state.push_back(i);
            
            // 存储二进制表示中的i的1的个数
            cnt[i] = sum(i);
        }
        
    // 状态计算
    for (int i = 1; i <= n + 2; i++)// 这里计算到n+2，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j < state.size(); j++)
            for (int k = 0; k < state.size(); k++)
            {
                int a = state[j], b = state[k];
                // 摆放的状态a、b不能存在摆放在无法摆放的位置上的情况
                if (g[i - 1] & a || g[i] & b)
                    continue;
                    
                for (int l = 0; l < state.size(); l++)
                {
                    int c = state[l];
                    /*
                        摆放的状态c不能存在摆放在无法摆放的位置上的情况，
                        但是这里无需判断，因为摆放的状态c如果存在摆放在无法摆放的位置上的情况的话，
                        与其相关的状态表示（f[?][c][?]）的结果，在状态计算的过程中，一定能保证其为0，
                        不会影响我们最终得到正确的答案
                    */
                    
                    /*
                        三个合法的状态间的合法状态转移，要满足以下条件：
                            1、a&b、a&c、b&c（位运算）的结果要等于0
                    */
                    if (a & b || a & c || b & c)
                        continue;
                        
                    /*
                        如果i&1的结果为1，则(i-1)&1的结果一定为0，反之亦然，
                        所以基于这个道理，就可以实现滚动数组
                    */
                    if (i == 1)
                        f[i & 1][0][b] = max(f[i & 1][0][b], f[i - 1 & 1][0][0] + cnt[b]);
                    if (i == 2)
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][0][a] + cnt[b]);
                    if (i > 2)
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][c][a] + cnt[b]);
                }
            }
    
    // 根据状态表示，直接输出结果
    printf("%d\n", f[n + 2 & 1][0][0]);
    
    return 0;
}

愤怒的小鸟

• 状态表示：f[s]（f[s]表示，在，由，覆盖的点的状态为s的每种覆盖方法所耗费的小鸟的数量，组成的集合，中，的最小值）

• 状态计算：f[k|path[i][j]]=min(f[k|path[i][j]],f[k]+1)（其中，k为原本覆盖的点的状态，i为状态k中还没有被覆盖的点中的随便一个点，path[i][j]表示由第i个点和第j个点（j∈{0,1,2,…,n-1}）所确定的经过原点的开口向下的抛物线所能够覆盖的点的状态，很显然该抛物线一定是能够覆盖第i个点的）

愤怒的小鸟

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

const int N = 18;
const int S = 1 << N;
const double EPS = 1e-6;

int n, m;
PDD g[N];// 存储每个点的坐标
int path[N][N];// path[i][j]表示，由第i个点和第j个点所确定的经过原点的开口向下的抛物线所能够覆盖的点，的状态
int f[S];// 状态表示

// 判断两个浮点数是否相等
bool check(double a, double b)
{
    if (fabs(a - b) < EPS)// 当这两个浮点数的差值小于一个很小的数时，则可视这两个浮点数相等
        return 1;
        
    return 0;
}

int main()
{
    int t;
    scanf("%d", &t);
    
    while (t--)
    {
        scanf("%d %d", &n, &m);// 这个m在本题中，其实没啥用
        
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &g[i].first, &g[i].second);
            
        memset(path, 0, sizeof path);
        for (int i = 0; i < n; i++)
        {
            // 经过原点的开口向下的抛物线可能存在只覆盖一个点的特殊情况
            path[i][i] = 1 << i;// 处理特殊情况
            
            for (int j = 0; j < n; j++)
            {
                double x1 = g[i].first, y1 = g[i].second;
                double x2 = g[j].first, y2 = g[j].second;
                
                if (check(x1, x2))// 两个横坐标相同的点，无法确定一条经过原点的开口向下的抛物线
                    continue;
                
                /*
                    抛物线的一般式方程为y=a*x^2+b*x+c，
                    由于经过(0,0)这个点，所以方程可以简化为y=a*x^2+b*x，
                    当已知两个点(x1,y1)，(x2,y2)时，
                    即可求出a和b：
                        a=(y1/x1-y2/x2)/(x1-x2)
                        b=y1/x1-a*x1
                */
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                
                // 因为抛物线开口向下，所以a要小于0
                if (a >= 0)
                    continue;
                    
                for (int k = 0; k < n; k++)
                {
                    double x = g[k].first, y = g[k].second;
                    
                    if (check(a * x * x + b * x, y))
                        path[i][j] = path[i][j] + (1 << k);
                }
            }
        }
        
        memset(f, 0x3f, sizeof f);
        f[0] = 0;// 由状态表示可得
        
        for (int i = 0; i + 1 < 1 << n; i++)// 当i=((1<<n)-1)时，这个状态i已经没有必要再进行循环处理了
        {
            int x = 0;
            for (int j = 0; j < n; j++)
                if (!(i >> j & 1))
                {
                    x = j;// 找出状态i中还没有被覆盖的点中的随便一个点
                    break;
                }
                
            // 状态计算
            for (int j = 0; j < n; j++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }
        
        // 输出结果
        printf("%d\n", f[(1 << n) - 1]);
    }
    
    return 0;
}

习题

摘花生

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];// 状态表示
int w[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)// n次询问
    {
        int r, c;
        scanf("%d %d", &r, &c);
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                scanf("%d", &w[i][j]);
        
        // 状态计算
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= c; j++)
                f[i][j] = max(f[i - 1][j] + w[i][j], f[i][j - 1] + w[i][j]);
                
        printf("%d\n", f[r][c]);
    }
    return 0;
}

最低通行费

#include <iostream>

using namespace std;

const int N = 110;

int w[N][N];
int f[N][N];// 状态表示

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &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] = 0x3f3f3f3f;
                if (i > 1)
                    // 大于第1行时，才可能会从上面走过来
                    f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);
                if (j > 1)
                    // 大于第1列时，才可能会从左边走过来
                    f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);
            }
            
    printf("%d\n", f[n][n]);
    return 0;
}

方格取数

#include <iostream>

using namespace std;

const int N = 15;

int f[2 * N][N][N];// 状态表示
int w[N][N];

int main()
{
    int n;
    scanf("%d", &n);
    
    int r, c, x;
    while (cin >> r >> c >> x, r || c || x)
        w[r][c] = x;
        
    // 状态计算
    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)// j1和j2必须在正确的范围内
                {
                    int t = w[i1][j1];
                    
                    // 同一个方格中的数字只能取一次
                    
                    if (i1 != i2)
                        t += w[i2][j2];
                        
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);
                    f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1][i2] + t);
                }
            }
            
    printf("%d\n", f[n + n][n][n]);
    
    return 0;
}

传纸条（未完成！！！）

怪盗基德的滑翔翼

#include <iostream>

using namespace std;

const int N = 110;

int f[N];// 状态表示
int a[N];

int main()
{
    int k;
    scanf("%d", &k);
    while (k--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
            
        int res = 0;
        
        // 状态计算
        for (int i = 1; i <= n; i++)
        {
            f[i] = 1;
            for (int j = 1; j <= i - 1; 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 - 1; j++)
                if (a[j] > a[i])// 最长下降子序列
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        
        printf("%d\n", res);
    }
    return 0;
}

登山

#include <iostream>

using namespace std;

const int N = 1100;

int ful[N];// 状态表示
int fur[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    // 状态计算    
    for (int i = 1; i <= n; i++)
    {
        ful[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])// 从左到右的最长上升子序列
                ful[i] = max(ful[i], ful[j] + 1);
    }
    
    // 状态计算
    for (int i = n; i >= 1; i--)
    {
        fur[i] = 1;
        for (int j = n; j >= i + 1; j--)
            if (a[j] < a[i])// 从右到左的最长上升子序列
                fur[i] = max(fur[i], fur[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, ful[i] + fur[i] - 1);
        
    printf("%d\n", res);
    return 0;
}

合唱队形

#include <iostream>

using namespace std;

const int N = 110;

int ful[N];// 状态表示
int fur[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        
    // 状态计算  
    for (int i = 1; i <= n; i++)
    {
        ful[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])// 从左到右的最长上升子序列
                ful[i] = max(ful[i], ful[j] + 1);
    }
    
    // 状态计算  
    for (int i = n; i >= 1; i--)
    {
        fur[i] = 1;
        for (int j = n; j >= i + 1; j--)
            if (a[j] < a[i])// 从右到左的最长上升子序列
                fur[i] = max(fur[i], fur[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res, ful[i] + fur[i] - 1);
        
    printf("%d\n", n - res);
    return 0;
}

友好城市

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int f[N];// 状态表示
pair<int, int> a[N];

int main()
{
    int n;
    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);
    
    int res = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j <= i - 1; j++)
            if (a[j].second < a[i].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    return 0;
}

最大上升子序列和

#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int f[N];// 状态表示
int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
        
    int res = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for (int j = 1; j <= i - 1; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + a[i]);
                
        res = max(res, f[i]);
    }
    
    printf("%d\n", res);
    return 0;
}

拦截导弹

#include <iostream>

using namespace std;

const int N = 1e3 + 10;

int f[N], a[N];
int dd[N];// 存储的是当前每个非上升子序列的末尾值

int main()
{
    int n = 0;
    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]);
    }
    
    // 第二个问题用贪心的思路进行思考
    int cnt = 0;// 存储的是非上升子序列的个数
    for (int i = 0; i < n; i++)
    {
        int k = 0;// 从第0个非上升子序列开始遍历
        
        // 当没有遍历完非上升子序列，并且当前非上升子序列的末尾值小于当前元素，则需要继续遍历
        while (k < cnt && dd[k] < a[i])
            k++;
            
        dd[k] = a[i];
        
        if (k == cnt)// 这是需要单独开辟一个非上升子序列的情况
            cnt++;// 非上升子序列的个数加1
    }
    
    printf("%d\n%d\n", res, cnt);
    
    return 0;
}

导弹防御系统

• 迭代加深求最小值

#include <iostream>

using namespace std;

const int N = 55;

int a[N];
int uu[N];// 存储的是当前每个上升子序列的末尾值
int dd[N];// 存储的是当前每个下降子序列的末尾值
int n;

/*
    depth：上升子序列的个数和下降子序列的个数的总和的上限
    u：从下标为u开始，遍历a数组中的每个元素
    cntuu：上升子序列的个数
    cntdd：下降子序列的个数
*/
bool dfs(int depth, int u, int cntuu, int cntdd)
{
    // 当上升子序列的个数和下降子序列的个数的总和大于depth时，则需要继续进行迭代加深
    if (cntuu + cntdd > depth)
        return false;
        
    // 当u等于n时，表示已经遍历完a数组中的所有元素，即已经找到最优解，因为u是从0开始的
    if (u == n)
        return true;
        
    // 先判断把当前元素放到上升子序列的末尾
    bool flag = false;
    for (int i = 1; i <= cntuu; i++)// 找到第一个放到上升子序列的末尾的位置，即为最合适的位置
        if (a[u] > uu[i])
        {
            int t = uu[i];
            uu[i] = a[u];
            if (dfs(depth, u + 1, cntuu, cntdd))
                return true;
            uu[i] = t;// 状态还原，也称恢复现场
            flag = true;
            break;// 这里的break，就是优化，因为当前就是最合适的位置
        }
    if (!flag)// 如果没有找到能放到上升子序列的末尾的位置，则当前元素需要单独开辟一个上升子序列存放
    {
        uu[cntuu + 1] = a[u];
        if (dfs(depth, u + 1, cntuu + 1, cntdd))
            return true;
    }
    
    // 再判断把当前元素放到下降子序列的末尾
    flag = false;
    for (int i = 1; i <= cntdd; i++)// 找到第一个放到下降子序列的末尾的位置，即为最合适的位置
        if (a[u] < dd[i])
        {
            int t = dd[i];
            dd[i] = a[u];
            if (dfs(depth, u + 1, cntuu, cntdd))
                return true;
            dd[i] = t;// 状态还原，也称恢复现场
            flag = true;
            break;// 这里的break，就是优化，因为当前就是最合适的位置
        }
    if (!flag)// 如果没有找到能放到下降子序列的末尾的位置，则当前元素需要单独开辟一个下降子序列存放
    {
        dd[cntdd + 1] = a[u];
        if (dfs(depth, u + 1, cntuu, cntdd + 1))
            return true;
    }
    
    // 如果都不满足，即返回false
    return false;
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
            
        int depth = 0;// 存储的是上升子序列的个数和下降子序列的个数的总和的上限
        
        /*
            这个上限每次往上加1，
            直至在当前上限进行dfs时能找到最优解，
            这种dfs求最小值的方法被称为迭代加深求最小值
        */
        while (!dfs(depth, 0, 0, 0))
            depth++;
            
        printf("%d\n", depth);
    }
    
    return 0;
}

最长公共上升子序列

• 优化版，对代码作等价变形，直接降低时间复杂度

#include <iostream>

using namespace std;

const int N = 3e3 + 10;

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

int main()
{
    int n;
    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 = 1;
        
        for (int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
            
            if (b[j] < a[i])
                maxv = max(maxv, f[i - 1][j] + 1);
                
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], maxv);
        }
    }
    
    int res = 0;
    for (int j = 1; j <= n; j++)
        res = max(res, f[n][j]);
        
    printf("%d\n", res);
    
    return 0;
}

采药

#include <iostream>

using namespace std;

const int T = 1e3 + 10;

int f[T];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        for (int j = m; j >= a; j--)
            f[j] = max(f[j], f[j - a] + b);
    }
    printf("%d\n", f[m]);
    return 0;
}

装箱问题

#include <iostream>

using namespace std;

const int V = 2e4 + 10;

int f[V];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        for (int j = m; j >= a; j--)
            if (f[j - a] + a <= m)
                f[j] = max(f[j], f[j - a] + a);
    }
    printf("%d\n", m - f[m]);
    return 0;
}

宠物小精灵之收服

#include <iostream>

using namespace std;

const int N = 100 + 10;
const int V1 = 1e3 + 10;
const int V2 = 500 + 10;

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int f[V1][V2];

int main()
{
    int v1, v2, n;
    scanf("%d %d %d", &v1, &v2, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        for (int j = v1; j >= a; j--)
            for (int k = v2 - 1; k >= b; k--)
                f[j][k] = max(f[j][k], f[j - a][k - b] + 1);
    }
    
    // 输出收服的精灵个数的最大值
    printf("%d ", f[v1][v2 - 1]);
    
    // 在收服的精灵个数最多的情况下，令皮卡丘受到的伤害最小
    for (int i = 0; i <= v2 - 1; i++)
        if (f[v1][i] == f[v1][v2 - 1])
        {
            // 输出皮卡丘的剩余体力
            printf("%d\n", v2 - i);
            break;
        }
        
    return 0;
}

数字组合

#include <iostream>

using namespace std;

const int M = 1e4 + 10;

int f[M];

// 一维数组优化01背包问题
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 根据状态表示可得，f[0][0]=1
    f[0] = 1;
    
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = m; j >= x; j--)
            f[j] = f[j] + f[j - x];
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

买书

#include <iostream>

using namespace std;

const int N = 10;
const int M = 1e3 + 10;

int v[N];
int f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和4件物品，每件物品的体积为10,20,50,100，每件物品可以使用无限次。
		求解从第1~4件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    v[1] = 10, v[2] = 20, v[3] = 50, v[4] = 100;
    
    int m;
    scanf("%d", &m);
    
    // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
    f[0] = 1;
    
    // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
    // 状态计算的过程可以用一维数组去优化
    for (int i = 1; i <= 4; i++)
        /*
            这里用到了滚动数组的核心思想：
                用上一层的旧数据算出新数据，
                然后用新数据覆盖当前层的旧数据，
                以此类推再继续计算
                （上一层和当前层对应的是同一层下的两种不同状态）
        */
        // 第i件物品的体积为vi
        for (int j = v[i]; j <= m; j++)
            f[j] = f[j] + f[j - v[i]];
            
    printf("%d\n", f[m]);
    
    return 0;
}

货币系统

#include <iostream>

using namespace std;

const int N = 20;
const int M = 3e3 + 10;

long long f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和n件物品，每件物品的体积为v1,v2,v3,...,vi,...,vn，每件物品可以使用无限次。
		求解从第1~n件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
    f[0] = 1;
    
    // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
    // 状态计算的过程可以用一维数组去优化
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for (int j = x; j <= m; j++)
            f[j] = f[j] + f[j - x];
    }
    
    printf("%lld\n", f[m]);
    
    return 0;
}

货币系统

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

using namespace std;

const int N = 110;
const int M = 25010;

int a[N];
int f[M];

/*
	解题思路：
	1、把问题转化为背包问题：
		存在一个体积为m的背包和n件物品，每件物品的体积为v1,v2,v3,...,vi,...,vn，每件物品可以使用无限次。
		求解从第1~n件物品中选，并且总体积恰好等于m的组合数
	2、背包问题：
		状态表示：f[i,j]（f[i,j]表示，从第1~i件物品中选，并且总体积恰好等于j，的组合数）
		状态计算：f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	3、观察下面两个状态计算：
		f[i,j]=f[i-1,j]+f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
		f[i,j-vi]=      f[i-1,j-1*vi]+f[i-1,j-2*vi]+f[i-1,j-3*vi]+...
	4、可得如下状态计算：
		f[i,j]=f[i-1,j]+f[i,j-vi]
*/
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        
        // 把货币按货币面额的值从小到大进行排序，因为货币面额大的货币可以由货币面额小的货币表示出来
        sort(a + 1, a + 1 + n);
        
        memset(f, 0, sizeof f);
        // f[1][0],f[2][0],f[3][0],...,f[count][0]的值都是1，因为要让总体积恰好等于0，则表示什么物品都不选，就是1种方案
        f[0] = 1;
        
        int res = n;// 存储当前货币系统可以简化为多少个货币
        
        // 状态计算：f[i,j]=f[i-1,j]+f[i,j-vi]
        // 状态计算的过程可以用一维数组去优化
        for (int i = 1; i <= n; i++)
        {
            for (int j = a[i]; j <= a[n]; j++)
                f[j] = f[j] + f[j - a[i]];
                
            // 货币面额大的货币可以由货币面额小的货币表示出来
            /*
                当此货币面额的货币除了能被其本身表示，还能由货币面额小的货币表示出来，
                则此货币面额的货币没有存在的必要，意味着这套货币系统可以进行简化
            */
            if (f[a[i]] > 1)
                res--;
        }
        
        printf("%d\n", res);
    }
    return 0;
}

多重背包问题 III

#include <iostream>
#include <cstring>

using namespace std;

const int V = 2e4 + 10;

int f[V];// 当前层的状态表示
int g[V];// 存储上一层的状态表示
int q[V];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是g数组的下标

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        
        memcpy(g, f, sizeof f);// 存储上一层的状态表示
        
        // 按照余数分类（mod v）
        for (int j = 0; j < v; j++)
        {
            // 一开始设定，队头为0，队尾为-1
            int hh = 0, tt = -1;
            
            // 当前层中的状态只会从上一层中余数相等（mod v）的状态转移过来    
            for (int k = j; k <= m; k += v)
            {
                // 判断队头对应的g数组的下标是否已经超出窗口的范围
                // 对于前层中的任意一个状态，在容量允许的条件下，我们会向前数s个
                // 注意，滑动窗口的长度为s+1，不是s
                if (hh <= tt && q[hh] < k - s * v)
                    hh++;

                /*
                    为了让滑动窗口在滑动的过程中，
                    同一下标所对应的状态值保持不变（因为这样才能进行比较，才能使用单调队列求滑动窗口中的最大值），
                    经过发现，我们可以把滑动窗口中的每个状态相对于余数j来说，加了多少个v，就减去几个w即可！！！
                    
                    当队列不为空，
                    且队尾对应的g数组的下标的状态的值（值为：g[q[tt]]-(q[tt]-j)/v*w）小于等于当前遍历到的状态的值（值为：g[k]-(k-j)/v*w），
                    则弹出队尾元素，保证队列的单调性
                */
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                    tt--;
                q[++tt] = k;// 这里的q数组记录的值是g数组的下标
                
                /*
                    经过发现，当前层的当前状态f[k]的值为g数组当前滑动窗口中的最大值，
                    即g[q[hh]]+(k-q[hh])/v*w
                */
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    
    // 输出结果
    printf("%d\n", f[m]);
    
    return 0;
}

庆功会

#include <iostream>

using namespace std;

const int N = 500 + 10;
const int M = 6e3 + 10;

int f[M];

// 一维数组优化多重背包问题
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        for (int j = m; j >= 1; j--)
            for (int k = 0; k <= s && k * v <= j; k++)
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    printf("%d\n", f[m]);
    return 0;
}

混合背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;

int f[M];// 当前层的状态表示
int g[M];// 存储上一层的状态表示
int q[M];// 滑动窗口的数组（用数组模拟队列），这里的q数组记录的值是g数组的下标

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int v, w, s;
        scanf("%d %d %d", &v, &w, &s);
        
        if (s == -1)// 01背包问题
        {
            for (int j = m; j >= v; j--)
                f[j] = max(f[j], f[j - v] + w);
        }
        else if (s == 0)// 完全背包问题
        {
            for (int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else// 单调队列优化多重背包问题
        {
            // 按照余数分类（mod v）
            for (int j = 0; j < v; j++)
            {
                // 一开始设定，队头为0，队尾为-1
                int hh = 0, tt = -1;
                
                // 当前层中的状态只会从上一层中余数相等（mod v）的状态转移过来
                for (int k = j; k <= m; k += v)
                {
                    // 判断队头对应的g数组的下标是否已经超出窗口的范围
                    // 对于前层中的任意一个状态，在容量允许的条件下，我们会向前数s个
                    // 注意，滑动窗口的长度为s+1，不是s
                    if (hh <= tt && q[hh] < k - s * v)
                        hh++;
                        
                    /*
                        为了让滑动窗口在滑动的过程中，
                        同一下标所对应的状态值保持不变（因为这样才能进行比较，才能使用单调队列求滑动窗口中的最大值），
                        经过发现，我们可以把滑动窗口中的每个状态相对于余数j来说，加了多少个v，就减去几个w即可！！！
                        
                        当队列不为空，
                        且队尾对应的g数组的下标的状态的值（值为：g[q[tt]]-(q[tt]-j)/v*w）小于等于当前遍历到的状态的值（值为：g[k]-(k-j)/v*w），
                        则弹出队尾元素，保证队列的单调性
                    */
                    while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
                        tt--;
                    q[++tt] = k;// 这里的q数组记录的值是g数组的下标
                    
                    /*
                        经过发现，当前层的当前状态f[k]的值为g数组当前滑动窗口中的最大值，
                        即g[q[hh]]+(k-q[hh])/v*w
                    */
                    f[k] = g[q[hh]] + (k - q[hh]) / v * w;
                }
            }
        }
        
        memcpy(g, f, sizeof f);// 存储上一层的状态表示
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

二维费用的背包问题

#include <iostream>

using namespace std;

const int N = 1e3 + 10;
const int V1 = 100 + 10;
const int V2 = 100 + 10;

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int f[V1][V2];

int main()
{
    int n, v1, v2;
    scanf("%d %d %d", &n, &v1, &v2);
    
    for (int i = 1; i <= n; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        for (int j = v1; j >= a; j--)
            for (int k = v2; k >= b; k--)
                f[j][k] = max(f[j][k], f[j - a][k - b] + w);
    }
    
    printf("%d\n", f[v1][v2]);
    
    return 0;
}

潜水员

#include <iostream>
#include <cstring>

using namespace std;

const int V1 = 22;
const int V2 = 80;

int f[V1][V2];

/*
    二维体积01背包问题，状态表示是三维的，
    模拟01背包问题用一维数组优化的方式，
    可以用二维数组去优化二维体积01背包问题
*/
int main()
{
    int v1, v2, n;
    scanf("%d %d %d", &v1, &v2, &n);
    
    memset(f, 0x3f, sizeof f);// 把无意义的状态赋值为0x3f3f3f3f
    f[0][0] = 0;// 根据状态表示可得，f[0][0]=0
    
    for (int i = 1; i <= n; i++)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        
        // 状态计算
        for (int j = v1; j >= 0; j--)
            for (int k = v2; k >= 0; k--)
                // 当j-a、k-b的值为负数时，则视为从0转移过来
                f[j][k] = min(f[j][k], f[max(0, j - a)][max(0, k - b)] + w);
    }
    
    printf("%d\n", f[v1][v2]);
    
    return 0;
}

机器分配

#include <iostream>

using namespace std;

const int N = 15;
const int M = 20;

int f[N][M];
int v[N][M];
int w[N][M];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int k = 1; k <= m; k++)
        {
            v[i][k] = k;
            scanf("%d", &w[i][k]);
        }
        
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for (int k = 1; k <= m; k++)
                if (j >= v[i][k])
                    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
        }
        
    printf("%d\n", f[n][m]);
    
    // 此时，f[n][m]存的就是总价值最大的结果
    
    int j = m;
    // 从结果往前推，输出任意合法方案即可
    for (int i = n; i >= 1; i--)
        for (int k = m; k >= 0; k--)
            if (j >= v[i][k] && f[i][j] == f[i - 1][j - v[i][k]] + w[i][k])
            {
                printf("%d %d\n", i, k);
                j -= k;
                break;
            }
            
    return 0;
}

开心的金明

#include <iostream>

using namespace std;

const int N = 30;
const int M = 3e4 + 10;

int f[M];

// 一维数组优化01背包问题
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int v, p;
        scanf("%d %d", &v, &p);
        for (int j = m ; j >= 0; j--)
            if (j >= v)
                f[j] = max(f[j], f[j - v] + v * p);
    }
    
    printf("%d\n", f[m]);
    
    return 0;
}

有依赖的背包问题

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;
const int V = 110;
const int M = 110;

int v[N], w[N];

int h[N];// 存储每个节点对应的单链表的表头所指向的idx
int e[M];// 存储第idx条边所指向的节点
int ne[M];// 存储第idx条边所指向的节点所指向的idx
int idx;// 表示当前用到第idx条边

int f[N][V];// 状态表示
int n, volume;

void add(int a, int b)// 插入一条a节点指向b节点的边
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs(int u)
{
    /*
        先把当前子树中的根节点（即u节点）排除掉，因此要先把u节点的体积去掉
        
        然后可以把若干个子节点看成若干组物品，
        每组物品中根据给当前子节点分配的不同的体积对应有不同的物品，即可视为每组物品中有若干件物品，
        每件物品可能有不同的价值（因为给当前子节点分配的不同的体积，可能会对应得到不同的价值），
        每一组物品中最多只能选一件物品（因为每个子节点只能选一次）
        
        此时的思路可以用分组背包问题去考虑，
        结合分组背包问题的状态表示去理解，
        实际操作和用一维数组去优化分组背包问题的解题过程相似，
        此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组
    */
    
    /*
        此时的思路可以用分组背包问题去考虑，
        结合分组背包问题的状态表示去理解，
        实际操作和用一维数组去优化分组背包问题的解题过程相似，
        此时，f[u][j]的第二维度，等同于，用一维数组去优化分组背包问题的解题过程中的一维数组
    */
    for (int i = h[u]; i != -1; i = ne[i])// 依次遍历每组物品（循环物品组）
    {
        // 要结合树形DP进行分析，所以要先进行递归操作
        dfs(e[i]);
        
        for (int j = volume - v[u]; j >= 0; j--)// 先把u节点的体积去掉，然后体积从大到小循环（循环体积）
            /*
                每组物品中根据给当前子节点分配的不同的体积对应有不同的物品，即可视为每组物品中有若干件物品，
                每件物品可能有不同的价值（因为给当前子节点分配的不同的体积，可能会对应得到不同的价值），
                每一组物品中最多只能选一件物品（因为每个子节点只能选一次）
            */
            for (int k = 1; k <= j; k++)// 遍历给当前子节点分配的体积（循环决策）
                f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);// 注意，通过dfs操作回溯后，这里的f[e[i]][k]是本题目状态表示的含义
    }
    
    // 到这里为止，f[u][j]并不是本题目状态表示的含义，因为还没有把当前子树中的根节点（即u节点）选上
    
    // 按照本题目状态表示的含义，要把当前子树中的根节点（即u节点）也选上
    for (int j = volume; j >= v[u]; j--)// 注意，这里一定要从大到小循环
        f[u][j] = f[u][j - v[u]] + w[u];
    // 体积不够，则无法选择当前子树中的根节点（即u节点）
    for (int j = 0; j < v[u]; j++) 
        f[u][j] = 0;// 即为0
}

int main()
{
    scanf("%d %d", &n, &volume);
    
    // 初始化每个节点对应的单链表的表头所指向的idx为-1，表示每个节点与其它节点都不直接相连
    memset(h, -1, sizeof h);
    
    int root;
    for (int i = 1; i <= n; i++)
    {
        int p;
        scanf("%d %d %d", &v[i], &w[i], &p);
        
        if (p == -1)
            root = i;
        else
            add(p, i);
    }
    
    // 从根结点开始进行，状态计算
    dfs(root);
    
    // 输出结果
    printf("%d\n", f[root][volume]);
    
    return 0;
}

背包问题求方案数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;
const int MOD = 1e9 + 7;

/*
    f[i][j]的二维状态表示：f[i,j]表示，在，由，只从前i件物品中选并且总体积恰好等于j的每种选法的总价值，组成的集合，中，的最大值
    g[i][j]的二维状态表示：g[i,j]表示，在f[i,j]取到最大值时，的方案数
*/
int f[M];// 一维优化
int g[M];// 一维优化

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);// 这一步很有必要，因为要结合f[i][j]的二维状态表示的含义去理解
    f[0] = 0;
    // 根据状态表示可得
    g[0] = 1;
    
    for (int i = 1; i <= n; i++)
    {
        int v, w;
        scanf("%d %d", &v, &w);
        
        for (int j = m; j >= v; j--)
        {
            int maxv = max(f[j], f[j - v] + w);
            
            int cnt = 0;// 记录当前情况下的方案数
            if (maxv == f[j])
                // 如果是不选择当前第i个物品时取到最大值，当前情况下的方案数要加上这种情况下的方案数
                cnt += g[j];
            if (maxv == f[j - v] + w)
                // 如果是选择当前第i个物品时取到最大值，当前情况下的方案数要加上这种情况下的方案数
                cnt += g[j - v];
                
            g[j] = cnt % MOD;
            
            f[j] = maxv;
        }
    }
    
    // 找到最优选法（即总价值最大）
    int t = 0;
    for (int j = 0; j <= m; j++)
        t = max(t, f[j]);
        
    // 最优选法（即总价值最大）的方案数
    int sum = 0;
    for (int j = 0; j <= m; j++)
        if (t == f[j])
            sum = (sum + g[j]) % MOD;
        
    // 输出最优选法（即总价值最大）的方案数
    printf("%d\n", sum);
    
    return 0;
}

背包问题求具体方案

#include <iostream>

using namespace std;

const int N = 1e3 + 10;
const int M = 1e3 + 10;

int f[N][M];
int v[N];
int w[N];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &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]);
        }
        
    // 此时，f[1][m]存的就是总价值最大的结果
        
    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])
        {
            printf("%d ", i);
            j -= v[i];
        }
    
    return 0;
}

能量石

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

using namespace std;

const int N = 100 + 10;
const int M = 1e4 + 10;

int f[M];// 一维数组优化

struct Stone
{
    int s, e, l;
    bool operator< (const Stone& t) const
    {
        /*
            经过分析，按每个能量石的s/l的值从小到大进行排序，依次考虑，
            是最优策略，可以得到最优解
            
            注意：
                不要写成除法形式（因为分母可能为0）：s / l < t.s / t.l
                要写成乘法形式：s * t.l < t.s * l
        */
        return s * t.l < t.s * l;
    }
}stone[N];

int main()
{
    int t;
    scanf("%d", &t);
    
    for (int c = 1; c <= t; c++)
    {
        int n;
        scanf("%d", &n);
        
        int m = 0;
        
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d %d", &stone[i].s, &stone[i].e, &stone[i].l);
            m += stone[i].s;
        }
        
        // 按每个能量石的s/l的值从小到大进行排序
        sort(stone, stone + n);
        
        // 根据状态表示可得
        memset(f, -0x3f, sizeof f);
        f[0] = 0;
        
        for (int i = 0; i < n; i++)
            for (int j = m; j >= stone[i].s; j--)
                // 状态计算
                f[j] = max(f[j], f[j - stone[i].s] + stone[i].e - (j - stone[i].s) * stone[i].l);
                
        int res = 0;
        for (int j = 0; j <= m; j++)
            res = max(res, f[j]);
            
        printf("Case #%d: %d\n", c, res);
    }
    
    return 0;
}

金明的预算方案

#include <iostream>
#include <vector>

using namespace std;

const int N = 65;
const int M = 32010;

pair<int, int> master[N];// 存储主件物品的信息
vector<pair<int, int>> annex[N];// 存储附件物品的信息，和其对应的主件物品关联
int f[M];

// 一维数组优化分组背包问题
int main()
{
    int m, n;
    scanf("%d %d", &m, &n);
    
    for (int i = 1; i <= n; i++)
    {
        int v, p, q;
        scanf("%d %d %d", &v, &p, &q);
        if (!q)
            master[i] = {v, v * p};
        else
            annex[q].push_back({v, v * p});
    }
    
    for (int i = 1; i <= n; i++)
        // 选附件物品时，必须要选上其对应的主件物品
        if (master[i].first)
            for (int j = m; j >= 0; j--)
                // 枚举每个主件物品和其对应的附件物品选取的所有方案
                for (int k = 0; k < 1 << annex[i].size(); k++)
                {
                    // 每个方案都包含主件物品
                    int v = master[i].first;
                    int w = master[i].second;
                    
                    for (int u = 0; u < annex[i].size(); u++)
                        // 判断当前这个方案附件物品选取的情况
                        if (k >> u & 1)
                        {
                            v += annex[i][u].first;
                            w += annex[i][u].second;
                        }
                        
                    if (j >= v)
                        f[j] = max(f[j], f[j - v] + w);
                }
                
    printf("%d\n", f[m]);
    
    return 0;
}

大盗阿福

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int f[N][2];// 状态表示
int w[N];

int main()
{
    int t;
    scanf("%d", &t);
    
    while (t--)
    {
        int n;
        scanf("%d", &n);
        
        for (int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
            
        // 根据状态表示可得
        f[0][0] = 0;
        f[0][1] = -0x3f3f3f3f;
        
        // 状态计算
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }
        
        printf("%d\n", max(f[n][0], f[n][1]));
    }
    
    return 0;
}

股票买卖 IV

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 100 + 10;

int f[N][M][2];// 状态表示
int w[N];

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
        
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);
    // 根据状态表示可得
    for (int i = 0; i <= n; i++)
        f[i][0][0] = 0;
        
    // 状态计算
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
        
    int res = 0;
    for (int j = 0; j <= m; j++)
        res = max(res, f[n][j][0]);
        
    printf("%d\n", res);
    
    return 0;
}

股票买卖 V

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int f[N][3];// 状态表示
int w[N];

int main()
{
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
        
    // 根据状态表示可得
    memset(f, -0x3f, sizeof f);
    f[0][2] = 0;
    
    // 状态计算
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }
    
    // 极端情况：股票一直在跌，此时最大利润为0
    printf("%d\n", max(f[n][1], f[n][2]));
    
    return 0;
}

设计密码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50 + 10;
const int M = 50 + 10;
const int MOD = 1e9 + 7;

int n;
char str[M];// 模式串
int ne[M];// 模式串的next数组
int f[N][M];// 状态表示

int main()
{
    scanf("%d", &n);
    scanf("%s", str + 1);// 从下标为1开始读入
    
    int m = strlen(str + 1);// 注意，这里要从下标为1开始计算模式串的长度
    
    // 求模式串的next数组的过程
    // i从2开始，是因为ne[1]=0，相当于规定了模式串相等部分的前缀和后缀的长度不能相同
    for (int i = 2, j = 0; i <= m; i++)
    {
        while (j && str[j + 1] != str[i]) 
            j = ne[j];
            
        if (str[j + 1] == str[i]) 
            j++;
            
        ne[i] = j;// 记录next数组的值
    }
    
    // 根据状态表示可得
    f[0][0] = 1;
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            for (int k = 'a'; k <= 'z'; k++)
            {
                int u = j;
                
                while (u && str[u + 1] != k)
                    u = ne[u];
                    
                if (str[u + 1] == k)
                    u++;
                    
                if (u < m)// 当u==m时，则没有必要进行状态计算，因为不符合题意
                    // 状态计算
                    f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }
            
    int res = 0;
    // 根据状态表示可得
    for (int j = 0; j < m; j++)
        res = (res + f[n][j]) % MOD;
        
    printf("%d\n", res);
    
    return 0;
}

修复DNA（未完成！！！）

小国王

#include <iostream>
#include <vector>

using namespace std;

const int N = 10 + 2;
const int K = 100 + 10;
const int S = 1 << 10;

typedef long long LL;

int n, k;
vector<int> state;// 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
int cnt[S];
vector<int> head[S];// 存储两个合法的状态间的合法状态转移
LL f[N][K][S];// 状态表示

// 判断二进制表示中的状态是否存在连续两个1的情况
bool check(int state)
{
    return !(state & (state >> 1));
}

// 计算二进制表示中的状态的1的个数
int count(int state)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        if (state >> i & 1)
            sum++;
    return sum;
}

int main()
{
    scanf("%d %d", &n, &k);
    
    for (int i = 0; i < 1 << n; i++)
        if (check(i))
        {
            // 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
            state.push_back(i);
            
            // 存储二进制表示中的i的1的个数
            cnt[i] = count(i);
        }
        
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            
            /*
                两个合法的状态间的合法状态转移，要满足以下条件：
                    1、a&b（位运算）的结果要等于0
                    2、a|b（位运算）的结果不存在连续两个1的情况
            */
            if ((a & b) == 0 && check(a | b))
                head[a].push_back(b);
        }
    
    // 根据状态表示可得    
    f[0][0][0] = 1;
    
    // 状态计算
    for (int i = 1; i <= n + 1; i++)// 这里计算到n+1，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j <= k; j++)
            for (int x = 0; x < state.size(); x++)
                for (int t : head[state[x]])
                {
                    int temp = cnt[state[x]];
                    if (j >= temp)
                        f[i][j][state[x]] += f[i - 1][j - temp][t];
                }
    
    // 根据状态表示，直接输出结果            
    printf("%lld\n", f[n + 1][k][0]);
    
    return 0;
}

玉米田

#include <iostream>
#include <vector>

using namespace std;

const int N = 14;
const int M = 12;
const int S = 1 << M;
const int MOD = 1e8;

int n, m;
int g[N];// 存储玉米地的情况
vector<int> state;// 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
vector<int> head[S];// 存储两个合法的状态间的合法状态转移
int f[N][S];// 状态表示

// 判断二进制表示中的状态是否存在连续两个1的情况
bool check(int state)
{
    return !(state & (state >> 1));
}

int main()
{
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int j = m - 1; j >= 0; j--)
        {
            int t;
            scanf("%d", &t);
            
            // 存储玉米地的情况
            g[i] = g[i] + (!t << j);
        }
        
    for (int i = 0; i < 1 << m; i++)
        if (check(i))
            // 存储所有，二进制表示中的状态不存在连续两个1的情况，的状态
            state.push_back(i);
            
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            
            /*
                两个合法的状态间的合法状态转移，要满足以下条件：
                    1、a&b（位运算）的结果要等于0
            */
            if ((a & b) == 0)
                head[a].push_back(b);
        }
        
    // 根据状态表示可得 
    f[0][0] = 1;
    
    // 状态计算
    for (int i = 1; i <= n + 1; i++)// 这里计算到n+1，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j < state.size(); j++)
        {
            // 摆放的状态state[j]不能存在摆放在不育的玉米地上的情况
            if (state[j] & g[i])
                continue;
            
            for (int t : head[state[j]])
            {
                // 摆放的状态t不能存在摆放在不育的玉米地上的情况
                if (t & g[i - 1])
                    continue;
                    
                f[i][state[j]] = (f[i][state[j]] + f[i - 1][t]) % MOD;
            }
        }
        
    // 根据状态表示，直接输出结果
    printf("%d\n", f[n + 1][0]);
    
    return 0;
}

炮兵阵地

#include <iostream>
#include <vector>

using namespace std;

const int N = 103;
const int M = 10;
const int S = 1 << M;

int n, m;
int g[N];// 存储网格地图的情况
vector<int> state;// 存储所有，二进制表示中的状态不存在连续三位中包含两个1及以上的情况，的状态
int cnt[S];
/*
    因为这道题目有空间限制，
    所以需要用滚动数组来进行优化处理，
    把第一维设为2即可
*/
int f[2][S][S];// 状态表示

// 判断二进制表示中的状态是否存在连续三位中包含两个1及以上的情况
bool check(int state)
{
    for (int i = 0; i < m; i++)
        /*
	        运算符的优先级：算术运算符 > 移位运算符 > 位运算符 > 逻辑运算符
            如果实在记不住运算符的优先级，那就加括号处理
        */
        if ((state >> i & 1) & (state >> i + 1 & 1) || (state >> i & 1) & (state >> i + 2 & 1))
            return false;

    return true;
}

// 计算二进制表示中的状态的1的个数
int sum(int state)
{
    int res = 0;
    for (int i = 0; i < m; i++)
        if (state >> i & 1)
            res++;
    return res;
}

int main()
{
    scanf("%d %d", &n, &m);
    
    for (int i = 1; i <= n; i++)
        for (int j = m - 1; j >= 0; j--)
        {
            char t;
            cin >> t;// cin在输入时能够帮我们过滤空格，scanf则不行，它会读入空格。如果这里使用scanf则会有问题
            
            // 存储网格地图的情况
            if (t == 'H')
                g[i] = g[i] + (1 << j);
        }
        
    for (int i = 0; i < 1 << m; i++)
        if (check(i))
        {
            // 存储所有，二进制表示中的状态不存在连续三位中包含两个1及以上的情况，的状态
            state.push_back(i);
            
            // 存储二进制表示中的i的1的个数
            cnt[i] = sum(i);
        }
        
    // 状态计算
    for (int i = 1; i <= n + 2; i++)// 这里计算到n+2，是为了可以根据状态表示，直接输出结果
        for (int j = 0; j < state.size(); j++)
            for (int k = 0; k < state.size(); k++)
            {
                int a = state[j], b = state[k];
                // 摆放的状态a、b不能存在摆放在无法摆放的位置上的情况
                if (g[i - 1] & a || g[i] & b)
                    continue;
                    
                for (int l = 0; l < state.size(); l++)
                {
                    int c = state[l];
                    /*
                        摆放的状态c不能存在摆放在无法摆放的位置上的情况，
                        但是这里无需判断，因为摆放的状态c如果存在摆放在无法摆放的位置上的情况的话，
                        与其相关的状态表示（f[?][c][?]）的结果，在状态计算的过程中，一定能保证其为0，
                        不会影响我们最终得到正确的答案
                    */
                    
                    /*
                        三个合法的状态间的合法状态转移，要满足以下条件：
                            1、a&b、a&c、b&c（位运算）的结果要等于0
                    */
                    if (a & b || a & c || b & c)
                        continue;
                        
                    /*
                        如果i&1的结果为1，则(i-1)&1的结果一定为0，反之亦然，
                        所以基于这个道理，就可以实现滚动数组
                    */
                    if (i == 1)
                        f[i & 1][0][b] = max(f[i & 1][0][b], f[i - 1 & 1][0][0] + cnt[b]);
                    if (i == 2)
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][0][a] + cnt[b]);
                    if (i > 2)
                        f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][c][a] + cnt[b]);
                }
            }
    
    // 根据状态表示，直接输出结果
    printf("%d\n", f[n + 2 & 1][0][0]);
    
    return 0;
}

愤怒的小鸟

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

const int N = 18;
const int S = 1 << N;
const double EPS = 1e-6;

int n, m;
PDD g[N];// 存储每个点的坐标
int path[N][N];// path[i][j]表示，由第i个点和第j个点所确定的经过原点的开口向下的抛物线所能够覆盖的点，的状态
int f[S];// 状态表示

// 判断两个浮点数是否相等
bool check(double a, double b)
{
    if (fabs(a - b) < EPS)// 当这两个浮点数的差值小于一个很小的数时，则可视这两个浮点数相等
        return 1;
        
    return 0;
}

int main()
{
    int t;
    scanf("%d", &t);
    
    while (t--)
    {
        scanf("%d %d", &n, &m);// 这个m在本题中，其实没啥用
        
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &g[i].first, &g[i].second);
            
        memset(path, 0, sizeof path);
        for (int i = 0; i < n; i++)
        {
            // 经过原点的开口向下的抛物线可能存在只覆盖一个点的特殊情况
            path[i][i] = 1 << i;// 处理特殊情况
            
            for (int j = 0; j < n; j++)
            {
                double x1 = g[i].first, y1 = g[i].second;
                double x2 = g[j].first, y2 = g[j].second;
                
                if (check(x1, x2))// 两个横坐标相同的点，无法确定一条经过原点的开口向下的抛物线
                    continue;
                
                /*
                    抛物线的一般式方程为y=a*x^2+b*x+c，
                    由于经过(0,0)这个点，所以方程可以简化为y=a*x^2+b*x，
                    当已知两个点(x1,y1)，(x2,y2)时，
                    即可求出a和b：
                        a=(y1/x1-y2/x2)/(x1-x2)
                        b=y1/x1-a*x1
                */
                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
                double b = y1 / x1 - a * x1;
                
                // 因为抛物线开口向下，所以a要小于0
                if (a >= 0)
                    continue;
                    
                for (int k = 0; k < n; k++)
                {
                    double x = g[k].first, y = g[k].second;
                    
                    if (check(a * x * x + b * x, y))
                        path[i][j] = path[i][j] + (1 << k);
                }
            }
        }
        
        memset(f, 0x3f, sizeof f);
        f[0] = 0;// 由状态表示可得
        
        for (int i = 0; i + 1 < 1 << n; i++)// 当i=((1<<n)-1)时，这个状态i已经没有必要再进行循环处理了
        {
            int x = 0;
            for (int j = 0; j < n; j++)
                if (!(i >> j & 1))
                {
                    x = j;// 找出状态i中还没有被覆盖的点中的随便一个点
                    break;
                }
                
            // 状态计算
            for (int j = 0; j < n; j++)
                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
        }
        
        // 输出结果
        printf("%d\n", f[(1 << n) - 1]);
    }
    
    return 0;
}

宝藏（未完成！！！）