动态规划刷题记录（1）

动态规划问题在这两年蓝桥杯频繁出现，它既是一个重点，也是一个难点。

1、整数拆分

 这道题目的思路其实很直接，基本上一眼就可以看出来这是完全背包问题的应用+一维优化。

整数N相当于是背包体积，2的幂相当于是物品体积，每种物品可以拿无数次，问你方案有多少种。数据范围已经给你了，我们可以确定最多用到2的20次方，因为2的21次方已经大于一百万了，于是我们先把2的前二十次方预处理。

接下来就是重点，我们定义集合f(i ，j)表示从前i个物品挑选使用，占用的体积为j的方案数，状态划分就是是否用了第i个物品？用了多少个？可能你没学过完全背包会看不懂我在说什么，背包问题作为动态规划的典型问题最好还是花时间学习

上代码：

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

using namespace std;

#define N 1000100

const int mod = 1e9;

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

int main()
{
    cin >> n;

    int t = 1;
    for (int i = 0 ;i <= 21 ;i ++) p[i] = t ,t *= 2;

    f[0] = 1;
    for (int i = 0 ;i <= 21 ;i ++)
        for (int j = p[i] ;j <= n ;j ++)
            f[j] = (f[j] + f[j - p[i]]) % mod;

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

2、最大的和

这道题目说白了就是让你在一行数中找到其中的两段，使这两段的和最大。这是一个动态规划问题，思路主要有两种：

（1）我们先来想想如果题目问你的是让你找到一个最大子段和，我们怎么解决？定义集合f(i)表示前i个数中的最大子段和，w[i]用来记录这n个数。那么以最大子段是否包含第i个数为集合划分依据：

     区间不包含w[i]: f[i] = f[i - 1];
    区间包含w[i]: f[i] = 以w[i - 1]结尾的最大连续区间和 + w[i];

那么很明显，我们缺少一个数据用来表示 以w[i - 1]结尾的最大连续区间和，所以我们再开一个区间h（i）用来记录以w[i]结尾的最大子段和。h(i)同样需要我们来递推：

        区间只包含w[i]，也就是说a[i]一个数的和就大于了之前所有以w[i]结尾的子段和：h[i] = w[i];

        区间包含了w[i]: h[i] = h[i - 1] + w[i];

到这里我们就可以解决找到一个最大子段和的问题了，那么现在再想想题目的求两段最大子段和。我们完全可以正着推一遍，再反着来一遍，最后枚举中间点在哪就行了。

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

using namespace std;

#define N 1001000

int t ,f[N] ,h[N] ,g[N] ,w[N];

int main()
{
    cin >> t;
    while (t --)
    {
        int n;
        scanf("%d" ,&n);

        for (int i = 1 ;i <= n ; i ++) scanf("%d" ,&w[i]);//记录这n个数

        f[0] = g[0] = -1e9;//初始化数组，这里是个细节要注意，一般来说我们动态规划求最大值就需要初始化很小的数，求最小值就需要初始化一个很大的数。
        for (int i = 1 ;i <= n ;i ++)
        {
            h[i] = max(h[i - 1] ,0) + w[i];//其实就是h[i - 1] + w[i] 和 w[i]取最大值
            f[i] = max(f[i - 1] ,h[i]);//根据上面的递推公式
        }

        h[n + 1] = g[n + 1] = -1e9;//刚刚是1到n，现在我们n到1来一遍
        for (int i = n ;i >= 1 ;i --)
        {
            h[i] = max(h[i + 1] ,0) + w[i];
            g[i] = max(g[i + 1] ,h[i]);
        }

        int res = -1e9;
        for(int i = 1;i <= n;i ++) res = max(res, f[i] + g[i + 1]);//枚举断点，寻找最大值
        cout << res << endl;
    }

    return 0;
}

（2）第二种思路更好理解一点：f(i ,j ,0/1)表示考虑前 i个数，且已经选了 j个连续的子段，且第 i
个数是否在第 j 段中。

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

using namespace std;

#define N 50010

int f[N][3][2] ,a[N];

int main()
{
    int t;
    scanf("%d" ,&t);

    while (t --)
    {
        memset(f ,-0x3f ,sizeof(f));

        int n;
        scanf("%d" ,&n);

        f[0][0][0] = 0;
        for (int i = 1 ;i <= n ;i ++) scanf("%d" ,&a[i]);

        for (int i = 1 ;i <= n ; i ++)
        {
            for (int j = 0 ;j <= 2 ;j ++)
            {
                 f[i][j][1] = max(f[i - 1][j][1] + a[i] ,f[i][j][1]);//若选择第 i个数接在原先由第 i−1个数作为末尾的第 j段后面:
                 f[i][j][0] = max(max(f[i][j][1] ,f[i - 1][j][1]) ,f[i - 1][j][0]);//如果不选第i个数
                 if (j) f[i][j][1] = max(max(f[i - 1][j - 1][0] + a[i] ,f[i][j][1]) ,f[i - 1][j - 1][1] + a[i]);//如果第i个数单独开了一段
            }
        }

        cout << max(f[n][2][1] ,f[n][2][0]) << endl;
    } 
    return 0;

}