NOIP-DP
2024-03-13 12:16:51 # OI # Note

状态本质是图论中一个个点，转移对应一条条边

复杂度分析：状态数量 ×\times 状态计算

线性DP

  • 路径类
  • 序列类
  • 组合类

1.状态

  • 题目中有很多状态，而这些状态间存在某些关系的题目。

image.webp

所谓状态，就是你当前处于哪个场景的概念。

比如我现在手里有六个骰子，

那么就有 6×6×6{6}\times{6}\times{6} 也就是 216216 种场景，

变量的组合便是状态。

2.转移方程

状态与状态之间的关系（点与点之间的边）。

要根据具体题目进行设计。

典例

  • 斐波那契数列

这是最常见的一个递推。

那么怎么进行DP呢？

想想状态和什么有关系——当前这一项和前两项有关系，后两项与当前状态有关系。

image.webp

那么就有了DP的两种写法：

1.自己求别人

2.别人求自己

image.webp

根据题目选择不同的 DP\text{DP} 方式

3.记忆化搜索

image.webp

复杂度 O(N)O(N)

image.webp

特征方程法解通项公式。

闫式思考法

矩阵路线问题

  • 状态表示
    • fi,jf_{i,j}
    • 表示一类集合：所有从 (1,1)(1,1) 到 (i,j)(i,j) 的路线。
    • 属性：最大值/最小值/方案数。
  • 状态计算
    • 集合的划分
      • 划分依据：最后，本例中为最后一步从上面下来还是从左边过来。
        • 从上边过来：(1,1)→(i−1,j)→(i,j)(1,1)\to(i-1,j)\to(i,j)
        • 从左面过来：(1,1)→(i,j−1)→(i,j)(1,1)\to(i,j-1)\to(i,j)
        • 两部分取一个 max⁡\max，分而治之，将集合进行一个划分。
      • 划分原则：
        • 不重（求最值等无所谓）
        • 不漏
    • 计算顺序
      • 按照拓扑序计算，保证每个状态计算时它的依赖状态已经被计算过了。

截图：

image.png

方格取数

image.png

LIS

  • 状态表示
    • 集合：所有以 aia_i 结尾的严格单调上升子序列
    • 属性：Max/Min/数量
  • 状态计算
    • 集合——分而治之。
    • 通过最后一步划分：最后一步是 aia_i

A1017

正序倒叙分别求两遍最长上升子序列取最大值即可。

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        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; j++)
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        for(int i = n; i >= 1; i--)
        {
            f[i] = 1;
            for(int j = n; j > i; j--)
                if(a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        printf("%d\n", res);
    }
    return 0;
}
  • 状态划分
    • 先增后减，根据中间点分类。

A1014

#include <bits/stdc++.h>
using namespace std;

int f[1100];
int g[1100];
int n;
int a[1100];

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

A1012 友好城市

两岸，一边看作自变量，一边看作因变量，在自变量不断递增的过程中，因变量也要是单调递增的，对自变量排下序，对因变量求最长上升子序列，这样就转化成了一个最长上升子序列问题。

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
typedef pair<int, int> PII;

PII q[N];
int f[N];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &q[i].first, &q[i].second);
    sort(q + 1, q + n + 1);
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(q[i].second > q[j].second)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d\n", res);
    return 0;
}

A1016 最大上升子序列和

  • 状态表示
    • fif_i
    • 集合：所有以 aia_i 结尾的上升子序列
    • 属性：和的最大值
  • 状态计算：倒数第二个数
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

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

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        f[i] = a[i];
        for(int j = 1; j < i ; j++)
            if(a[i] > a[j])
                f[i] = max(f[i], f[j] + a[i]);
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

导弹拦截

  • 贪心流程：
    • 情况1：如果现有的子序列结尾都小于当前数，那么就创建新的子序列
    • 情况2：把当前数放到结尾大于等于它的最小的子序列后面。因为要把结尾尽可能大的保持住，这样后面才会有更多的机会。
  • 证明贪心正确性
    • 如何证明两个数相等？
      • A表示贪心算法得到的序列个数，B表示最优解 A≤B,B≤AA\le B,B\le A
      • 由于 B 是最优解，因此 B≤AB\le A
      • 使用调整法，假设最优解对应的方案和当前方案不同，那么必然会存在第一个不同的位置。贪心法一定会把这个数分配到一个大于等于它的最小的子序列的后面，最优解也会放到某个序列后面，它们之后的序列就可以是一样的，就可以把它们交换，使得贪心法成为最优解，同时没有增加子序列的个数，所以 A≤BA\le B。
      • 此题得证。

A1010

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

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

int main()
{
    while(cin >> q[n]) n++;
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        f[i] = 1;
        for(int j = 0; j < i; j++)
            if(q[j] >= q[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        int k = 0; // 枚举序列
        while(k < cnt && g[k] < q[i]) k++;
        g[k] = q[i]; // 第一个结尾大于等于该数的序列 | g 是单调的
        if(k >= cnt) cnt++; // 新开一个序列
    }
    cout << cnt << endl;
    return 0;
}

A187

每个位置有两种选择，两种决策，要考虑所有情况，没办法归类，只能直接爆搜。

#include <bits/stdc++.h>
using namespace std;
const int N = 55;

int n;
int q[N];
int up[N], down[N]; // 所有子序列中最后一个数的集合
int ans;

// BFS 占用空间太大 并且不好剪枝
void dfs(int u, int su, int sd) // 当前枚举到第几个数 上升子序列有多少 下降子序列有多少
{
    if(su + sd >= ans) return;
    if(u == n)
    {
        ans = su + sd; // 能到就可以更新
        return;
    }
    // 放到上升子序列里
    int k = 0;
    while(k < su && up[k] >= q[u]) k++; // q[u] > up[k] 且 up[k] 最大 | up数组单调递减
    int t = up[k]; // 备份 方便恢复现场
    up[k] = q[u];
    if(k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;
    // 放到下降子序列里
    k = 0;
    while(k < sd && down[k] <= q[u]) k++; // q[u] < down[k] 且 down[k] 最小 | down数组单调递增
    t = down[k];
    down[k] = q[u];
    if(k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i++) cin >> q[i];
        ans = n;
        dfs(0, 0, 0);
        cout << ans << endl;
    }
    return 0;
}

最长公共子序列

  • 状态表示
    • fi,jf_{i,j}
    • 集合：所有由第一个序列的前 ii 个字母，第二个序列的前 jj 个字母且以 bjb_j 结尾的公共上升子序列
    • 属性：最大长度
  • 状态计算
    • 分而治之，对每一个部分求最大值。
    • 所有包含 aia_i 的公共上升子序列
      • 根据倒数第二个元素划分。
      • fi,kf_{i,k}
    • 所有不包含 aia_i 的公共上升子序列：fi−1,jf_{i-1,j}
  • 优化
    • DP 的优化一般思路不变，只是对代码进行等价变形。

image.png

#include <bits/stdc++.h>
using namespace std;
const int N = 3010;

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

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &b[i]);
    for(int i = 1; i <= n; i++)
    {
        int maxv = 1;
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i - 1][j];
                // f[i][j] = max(f[i][j], 1); // 更新空集
                // for(int k = 1; k < j; k++) // 实际上就是在求 f[i][j] + 1 的前缀最大值不含第 j 位
                //     if(b[k] < a[i])
                //     {
                //         f[i][j] = max(f[i][j], f[i][k] + 1);
                //     }
            /* 等效代码 */
            if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1); // 维护 f[i][j] + 1 这个变量的前缀最大值
        }
    }
    for(int i = 1; i <= n; i++)
        res = max(res, f[n][i]);
    cout << res << endl;
    return 0;
}

组合数问题（杨辉三角）

image.webp

image.webp

过河卒但是没有🐎

image.webp

每个点的方案数等于左边数和上边数相加（记得初始化边界）。

那么这个东西斜起来看的话其实就是杨辉三角。

数字三角形

正常版

洛谷上有道滑雪，

第ii行有ii个数，

每次可以朝下或者朝右下走，

那么从第一行走到最后一行怎么走会使路径上的数和最大，

f[i][j]=max(f[i−1][j−1],f[i−1][j])f[i][j]=max(f[i-1][j-1],f[i-1][j])。

还是要记得初始化。

EX版

附加条件：%100\%100后最大

可以加一个条件，使得每个状态都%100\%100？

NO

会破坏它的最优子结构

判断最优子结构就是判断 DP 正确性的关键

也就是最优解不一定是用你所谓的最优解求出的

重点来了：DP题中题目每多一个条件，状态都可以再加一个维度

f[i][j][k]f[i][j][k]：走到ii，jj，和%100\%100为kk这件事是否可能(true/false)

image.webp

数字三角形3

必须经过 (n2\dfrac{n}{2}, n2\dfrac{n}{2}) 这个点。

数字三角形4

必须先走到某个点再走到最底层

个人想法：

把这看作两个过程，相当于先以这个点为终点跑一遍数字三角形，然后再以这个点为起点再跑一遍数字三角形，两段相加即可。

最长上升子序列（Longest Increasing Subsequence）

1.求最长长度

f[i]f[i] 代表 ii 必选且 ii 为最后一个数得到的最长上升子序列。

f[i]f[i] 至少等于 11，因为至少选 ii。

那么就可以求最长：

image.webp

2.求方案数

再开一个 g[i]g[i]，

g[i]g[i]代表以 ii 结尾最长的长度的方案数，

这是通解。

如下：

image.webp

遇到求方案数的问题都可以新开一个数组来记录方案数。

假如长度变长了，那么就 gi=gjg_i=g_j。

改一下写法的话就是像上图所示，如果是更新那就先置为0并且令它们相同，然后顺其自然的加上，相当于赋值了，而等于的情况正好也是加上，也就是稍微合并了一下操作。

3.输出一种方案数

  • 再开一个数组prepre记录每一个状态是从哪里走过来的。

pre[i]pre[i]=0就是前面没东西了

#include<bits/stdc++.h>
using namespace std;
int f[10000];//f[i]代表i必选且i为最后一个数得到的最长
int g[10000];//g[i]代表最长的长度的方案数
int pre[10000];//上一个状态是从哪里走过来的
int main()
{
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//至少为1
        g[i]=1;//自己是一个方案
        pre[i]=0;//前面没东西
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
            {
                int l=f[j]+1;
                if(l>f[i])
                {
                    f[i]=l;//更新最长长度,一定会进入下一分支
                    g[i]=0;//每周j的方案后面加上一个i长度不变
                    pre[i]=j;//更新i这个位置的状态是从j更新的
                }
                if(l==f[i])
                {
                    g[i]+=g[j];//新的方案数就等于原来的方案数加上新的方案数
                }
            }
    }
    int p,cnt=0;//从p开始走
    do
    {
        z[++cnt]=p;
        p=pre[p];
    }while(p!=0);
    reverse(z+1,z+cnt+1);
    return 0;
}

复杂度显然是n2n^2的。

4.P2501

题解

5.优化

要做到nlognnlogn ？

1.线段树

我们无非就是要在 1∼i−11\sim{i-1} 中找到一个 jj 使得 aj<aia_j<a_i 并且 f[j]f[j] 最大

那我们就建一颗线段树，范围 1∼m1{\sim}m

mm 是 max(a1∼an)max({a_1}\sim{a_n})，即所有数的最大值

假如 a[j],f[j]a[j],f[j] 都知道了

进行一个单点修改

每次找到一个 f[j]f[j] 就把它赋值给 aja_j，

这样当前询问 aia_i 只需要询问 1∼ai−11\sim a_i-1 区间中的最大值，

因为这样保证了之前的数都是小于 aia_i 的并且它们的 LIS 都已经求出。

询问的是什么？

从左向右扫的

询问的是所有小于 aia_i 的数

这样找到最大的 fjf_j

满足 aj<aja_j<a_j

还取到 aja_j 的最大值

那么 a[i]a[i] 就是 f[j]+1f[j]+1

2.二分

插播一条二分

关于c++的lower_bound与upper_bound函数的理解 )

当容器中的元素按照递增的顺序存储时，lower_bound函数返回容器中第一个大于等于目标值的位置，upper_bound函数返回容器中第一个大于目标值的位置。若容器中的元素都比目标值小则返回最后一个元素的下一个位置。(≥\ge)

如果容器中的元素是递减的应该怎么查找呢？这是可以借助c++内置的仿函数greater<data_type>()，相当于重新定义了比较规则。此时lower_bound_()查找的是容器中第一个小于等于目标值的元素的位置，而upper_bound()查找的是容器中第一个小于目标值的元素的位置就。如果容器中的元素都比目标值大则返回最后一个元素的下一个位置。(>>)

image.webp

详情见优先队列

解法

现在存在两个位置p1p1和p2p2且p1<p2p_1<p_2、ap1a_{p_1}>ap2a_{p_2}

f[p1]f[p_1]≤\lef[p2]f[p_2]

这意味着什么

这个p1p_1肯定是没有用的

p2p_2一定比p1p_1更优

这样就可以把p1p_1删掉了

栗子: 7 2 1 5 6 4 3 8 9

假如

f[7]=f[2]=1f[7]=f[2]=1

那么7就没有用了

没用的就给去了

image.webp

在这里4可以把5给替换掉

image.webp

在这里4又被替换成3

我们发现什么问题？

这个创造出来的序列的第ii个位置就是f[i]f[i]

比如a3a_3就是最长上升子序列为33的最小的那个（最优的）

cnt代表新建出来的序列的大小

aa代表建出来的序列

a[3]=f[a[3]]=3a[3]=f[a[3]]=3

但是这样做还是n2n^2的

z[i]z[i]存的是f[i]f[i]的下标

也就是z[f[i]]=iz[f[i]]=i

算出了f[i]f[i]那肯定就把f[i]f[i]放在新数组的第f[i]f[i]个位置

比如算出了f[8]=4f[8]=4,那么新数组的第44个位置就是44

新数组就是z[]z[]，它存的不是新的序列，而是新序列中每个数对应原序列的下标

答案就是z1−cntz_{1-cnt}

f[z[j]]=jf[z[j]]=j

代码：

#include<bits/stdc++.h>
using namespace std;
int z[233];
int f[233];
int a[233];
int main()
{
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//f[i]中为序列下标
        for(int j=1;j<=cnt;j++)//把循环变成二分就可以优化为 nlogn
        //枚举新序列中的数，更新f[i]
        {
            if(a[z[j]]<a[i])//z[j]为f[]=j的数在a中的下标
                f[i]=max(f[i],j+1);//枚举构造出的序列来更新这个f[i]
        }
        if(f[i]>cnt)//新序列可以加，因为保证了构造出来的序列中第i位的f[]值为i，第cnt位置的f[]的值为cnt，那么加一位
        {
            cnt++;
            z[cnt]=i;//放入第cnt位数在a中的下标
        }
        else
        {
            if(a[i]<a[z[f[i]]])//长度为f[i]的数在a中的下标，因为长度为f[i]和在z中下标为f[i]是等价的
                z[f[i]]=i;//存下标，拿比你小还比你强的来更新你
            //如果需要方案，就记录一下从哪转移过来的
        }
    }
    return 0;
}

image.png

image.webp

else if(a[i]<a[z[f[i]]]) z[f[i]]=i;

image.png

这句就是把5给更新成4

注意：这个新构造的序列并不是最长上升子序列，而是用来更新f[i]的

如果要方案的话就开个数组记录一下

但是这样解的个数不是很好算

再优化

可以用二分查找找出小于a[i]的最大的那个位置

加入一个二分替代枚举就可以达到nlognnlog_n

因为新构造的序列是按照f[]值单调递增的

所以我们只需要每次二分查找一个小于当前a[i]的最大的数就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int z[N];
int f[N];
int a[N];
int ef(int l,int r,int k)//l,r为z下标，k为a中下标
{
    while(l<r)
    {
        int mid=(l+r+1)>>1;//右中位数
        if(a[z[mid]]<a[k])
            l=mid;//l=mid,保证l永远小于，满足条件
        else r=mid-1;//缩小右区间
    }
    return l;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//f[i]中为序列下标
        // cout<<ef(1,cnt,i)<<endl;
        f[i]=max(f[i],ef(0,cnt,i)+1);
        // cout<<f[i]<<endl;
        /*
        for(int j=1;j<=cnt;j++)//把循环变成二分就可以优化为 nlogn
        //枚举新序列中的数，更新f[i]
        {
            if(a[z[j]]<a[i])//z[j]为f[]=j的数在a中的下标
                f[i]=max(f[i],j+1);//枚举构造出的序列来更新这个f[i]
        }
        */
        if(f[i]>cnt)//新序列可以加，因为保证了构造出来的序列中第i位的f[]值为i，第cnt位置的f[]的值为cnt，那么加一位
        {
            cnt++;
            z[cnt]=i;//放入第cnt位数在a中的下标
        }
        else
        {
            if(a[i]<a[z[f[i]]])//长度为f[i]的数在a中的下标，因为长度为f[i]和在z中下标为f[i]是等价的
                z[f[i]]=i;//存下标，拿比你小还比你强的来更新你
            //如果需要方案，就记录一下从哪转移过来的,在发生转移的时候记录一下pre
        }
    }
    //cnt即为最长上升子序列的长度
    // for(int i=1;i<=cnt;i++)
    // {
    //     printf("%d ",a[z[i]]);
    // }
    // for(int i=1;i<=n;i++)
    // {
    //     printf("%d ",a[i]);
    // }
    printf("%d ",n-cnt);
    return 0;
}

二分真的很难调

简单解释一下吧，

现在保证左端点满足条件，

不断微调右端点，

二分到最后让右端点与左端点合并，

而最后遇到相邻的情况，

mid要取右中位数（也就是如果是两个相邻的数，在取整的过程中取右端点）。

具体是不是这样我也说不清。

以上做法可以A掉P3902

练习题

滑雪：

一个 nn 行 mm 列的网格图，每个格子有一个高度，只能滑向四周比自己矮的格子，任选起点，问最多能滑多远。

从高往低滑和从低向高滑的答案是一样的。

用 fi,jf_{i,j} 表示从 i,ji,j 出发的最长长度。

即 fi,j=max(fx,y)+1f_{i,j}=max(f_{x,y})+1，其中 x,yx,y 为能滑到 i,ji,j 的格子。

就这样记忆化搜索。

可以将所有点的高度从小到大排序。

这一定是从排序后的数组的左边滑到右边。

那就可以从左向右进行 dp。

fif_i 代表滑到 xi,yix_i,y_i 这个位置时的最长长度，然后枚举 ii 左边的数并且满足相邻（∣xi−xj∣+∣yi−yj∣=1|x_i-x_j|+|y_i-y_j|=1）的数中，ff 值最大的那个，把它加一就可以更新 fif_i。

这样就可以保证转移是从左向右的，枚举 i,ji,j 就可以了。

最低点初始化为 0。

这个方法本质上就是拓扑排序+DP。

乌龟棋

在走的过程中，有六个变量在发生变化，其中五个可以用来表示状态，一个用来表示状态的值，即 fi,a1,a2,a3,a4f_{i,a_1,a_2,a_3,a_4}，其中第一维表示当前的位置，后面四维表示分别用了多少牌。

然后我们发现第一维其实没有必要，因为当前所在的位置可以通过后四维求解，于是就可以减少枚举，此谓之去除冗余状态。

至此的一些技巧：

  1. 状态设计（每有一个变量对应一个维度）
  2. 增加维度
  3. 求方案数
  4. 改变枚举顺序
  5. 消除冗余状态

背包DP

01背包

  • 状态表示
    • fi,jf_{i,j}
    • 集合：所有只从前 ii 个物品中选，且总体积不超过 jj 的选法的集合。
    • 属性：最大值/最小值
  • 划分依据：用最后一步来划分。
  • 状态计算：
    • 不选第 ii 个物品的所有方案
    • 选第 ii 个物品的所有方案

有nn件物品，一个背包，每个物品有重量和价值，在背包不超重的情况下，问得到价值的最大值。

  1. 设计DP状态

我们令dpi,jdp_{i,j}代在前ii个物品中进行选择，用了jj的体积所得到的最大价值之和。

  1. 转移方程

第ii个物体重量为wiw_i，价值为viv_i。

考虑完了前i−1i-1件物品后，我们开始考虑第ii件物品，这件物品可以选也可以不选，那么就可以在这两种情况中取较大值。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

  1. 滚动优化

我们发现更新第ii个物品的时候只会用到第i−1i-1行，之前的都相当于没有用了，所以就可以把第一维去掉，用旧状态代表i−1i-1行，用新状态代表第ii行，更新新状态的时候就是拿旧时的自己来更新现在的自己，根据转移方程，我们发现其实是拿体积较小的状态递推为体积较大的状态，所以我们更新的时候需要保留旧状态，所以从后向前遍历，这样就可以保证用来更新新状态的状态全部都是旧状态；若正向遍历，体积小的旧状态已经被更新为新状态，后面更新体积大的新状态会用被覆盖的新状态来更新，导致考虑了第ii个物品后接着又考虑了第ii个物品，这样就会导致每个物品会被拿多次（无穷背包）。

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

第二层循环的终止条件为j>=a[i]，因为之后无法转移，也就是无法装下第ii件物品。

习题：

P1060

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m;
int x[N],f[N],v[N],p[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&v[i],&p[i]);
        x[i]=v[i]*p[i];
    }
    for(int i=1;i<=m;i++)
        for(int j=n;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+x[i]);
        }
    printf("%d",f[n]);
}

P1048

#include<bits/stdc++.h>
//背包：N个物品，背包体积为M，第i个物品价值为Wi，体积为Vi;
//Vi之和<=M,使得价值最大，问：最大的价值之和; 
using namespace std;
int f[2005];//f[105][2005];
int w[100000];
int v[100000];
//f[i][j]变化量：前i个物品已经选好了，此时用了j的体积 ，所能获得的最大价值；
//第i+1个物品放不放进背包？
//f[i][j]------>f[i+1][j]
//转移f[i][j]----->f[i+1][j+Vi+1];+Wi+1;
int main ()
{
	int n,m;
	cin>>n;//背包大小 
	cin>>m;//药物数目 
	for(int i=1;i<=m;i++)
		cin>>v[i]>>w[i];
//	for(int i=0;i<=m;i++)//前i个物品已经决定好放不放进背包 ///O(nm)
//		for(int j=0;j<=n;j++)//当前用了j的体积 
//		{
//		//考虑i+1放不放
//		//Yes 
//			f[i+1][j+v[i+1]]=max(f[i+1][j+v[i+1]],f[i][j]+w[i+1]); 
//		//if(j>=v[i])////判断数组越不越界,如果不越界，那么可以选第i个 
//		//	f[i][j]=max(f[i-1][j]//不选第i个,f[i-1][j-v[i]]+w[i]//选第i个);
//		//No
//			f[i+1][j]=max(f[i+1][j],f[i][j]);//待写
//		//else //不能选第i个 
//		//	f[i][j]=max(f[i][j],f[i-1][j]);////别人求自己 
//		
//		}

//	for(int j=1;j<=n;j++)
//	{
//		ans=max(f[m][j],ans);
////		cout<<f[m][j]<<' '<<j<<endl;
//	}
		
	for(int i=1;i<=m;i++)//滚动数组优化，用新的覆盖旧的 
		for(int j=n;j>=v[i];j--)
			f[j]=max(f[j],f[j-v[i]]+w[i]);
	cout<<f[n];
	return 0;
}

求方案数

再开一个 gi,jg_{i,j} 代表当前状态的方案数

A11

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int MOD = 1e9 + 7;

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

int main()
{
    cin >> n >> m;
    memset(f, 0xc0, sizeof(f));
    f[0] = 0; // 容量恰好为 i 的最大价值
    g[0] = 1; // 的方案数
    // 注意题目要求的是不超过 i 体积 因此要找一个最大值
    for(int i = 0; i < n; i++)
    {
        int v, w;
        cin >> 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]) cnt += g[j];
            if(maxv == f[j - v] + w) cnt += g[j - v];
            g[j] = cnt % MOD;
            f[j] = maxv;
        }
    }
    int res = 0;
    for(int i = 0; i <= m; i++) res = max(res, f[i]);
    int cnt = 0;
    for(int i = 0; i <= m; i++)
        if(res == f[i])
            cnt = (cnt + g[i]) % MOD;
    cout << cnt << endl;
    return 0;
}

求方案

开一个 prei,jpre_{i,j} 表示 i,ji,j 这个状态是由 i−1i-1 的哪个状态转移而来就好。

A12

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

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

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

A1013

#include <bits/stdc++.h>
using namespace std;
const int N = 11, M = 17;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> w[i][j];
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k] + w[i][k]);
        }
    int k = m;
    for(int i = n; i >= 1; i--)
        for(int j = 0; j <= k; j++)
            if(f[i][k] == f[i - 1][k - j] + w[i][j])
            {
                way[i] = j;
                k -= j;
                break;
            }
    cout << f[n][m] << endl;
    for(int i = 1; i <= n; i++) cout << i << ' ' << way[i] << endl;
    return 0;
}

二维费用的背包问题

  • 状态表示
    • fi,j,kf_{i,j,k}
    • 集合：所有只从前 ii 个物品中选，并且总体积不超过 jj ，总重量不超过 kk 的所有选法。
    • 属性：最大值
  • 状态计算
    • 最后一步：最后一个物品，要么包含要么不包含。
    • 不包含：fi−1,j,kf_{i-1,j,k}
    • 包含：fi−1,j−vi,k−mi+wif_{i-1,j-v_i,k-m_i}+w_i

初始化分类

  • 初始化分类
    • 体积最多是 jj
      • 方案数：f0,i=1,i∈[0,m]∣f1=1f_{0,i}=1,i\in{[0,m]}\quad|\quad f_{1}=1
      • 最大价值：fi,k=0,i∈[0,n],k∈[0,m]∣fi=0,i∈[0,m]f_{i,k}=0,i\in[0,n],k\in[0,m]\quad|\quad f_i=0,i\in[0,m]
    • 体积恰好是 jj
      • 方案数：f0,0=1∣f0=1f_{0,0}=1\quad|\quad f_0=1
      • 最大价值：f0,0=0,f0,i=−∞,i∈[1,∞]∣f0=0,fi=−∞f_{0,0}=0,f_{0,i}=-\infty,i\in[1,\infty]\quad|\quad f_0=0,f_i=-\infty
      • 最小价值：f0,0=0,f0,i=∞,i∈[1,∞]∣f0=0,fi=∞f_{0,0}=0,f_{0,i}=\infty,i\in[1,\infty]\quad|\quad f_0=0,f_i=\infty
    • 体积至少是 jj
      • 方案数：f0,0=1∣f0=1f_{0,0}=1\quad|\quad f_0=1
      • 最小价值：f0,0=0,f0,i=∞,i∈[1,∞]∣f0=0,fi=∞f_{0,0}=0,f_{0,i}=\infty,i\in[1,\infty]\quad|\quad f_0=0,f_i=\infty

从集合的角度考虑，考虑前 0 个物品且花费体积为 0 这一个元素，或者说是状态，在不同集合的定义中可以被划分到哪个集合，剩下的集合的状态是如何。

AcWing1020 潜水员

  • 状态表示
    • 集合：所有从前 ii 个物品中选，且氧气至少是 jj，但其至少是 kk 的所有选法。
    • 属性：最小值
  • 状态计算
    • 划分依据：最后一个物品的选择情况。
    • 所有不含第 ii 个物品的所有选法：fi−1,j,kf_{i-1,j,k}
    • 所有包含第 ii 个物品的所有选法：fi−1,j−v1,k−v2+w+if_{i-1,j-v_1,k-v_2}+w+i
#include <bits/stdc++.h>
using namespace std;
const int N = 22, M = 80;

int n, m, k;
int f[N][M];

int main()
{
    cin >> n >> m >> k;
    memset(f, 0x3f, sizeof(f));
    f[0][0] = 0;
    while(k--)
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        for(int j = n; j >= 0; j--)
            for(int k = m; k >= 0; k--) // 至少是 j / k
                f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
    }
    cout << f[n][m] << endl;
    return 0;
}

无穷背包

按照直观的想法，那就再枚举一个 kk 表示这个物品选多少个。

但这样复杂度是 O(n3)O(n^3) 的，所以考虑优化。

对比01背包，最大的不同就是它可以通过自己来更新自己，所以我们只需要在原来的基础上加上这样一句话：

它可以自己更新自己。

自己最初没选第 ii 个，然后可以选一个、两个、三个、四个……

for(int i=1;i<=n;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-w[i]]+v[i]);
+		if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
	}

很简单，将滚动优化的第二维改为正向枚举即可，解释见上；

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

等效替换：

image.png

image.png

求方案数

  • 状态表示
    • 集合：所有只从前 ii 个物品中选，且总体积恰好是 jj 的方案的集合。
    • 属性：数量
  • 状态计算
    • 根据第 ii 个物品选几个来划分集合。
    • 0 个：fi−1,jf_{i-1,j}
    • k 个：fi−1,j−k×vif_{i-1,j-k\times v_i}

fi,j=fi−1,j+fi−1,j−vi×kf_{i,j}=f_{i-1,j}+f_{i-1,j-v_i\times{k}}

image.png

这里可以直接替换。

fi,j=fi−1,j+fi,j−vf_{i,j} = f_{i-1,j}+f_{i,j-v}

这是通过它们的层层递推关系得出的。

习题：

P1616

#include<bits/stdc++.h>
#define int long long
using namespace std;
//w[i]价值
//v[i]花费
const int N=1000+5,M=100000+5;
int n,m,w[N],v[N],f[N][M];
int main()
{
	scanf("%lld%lld",&m,&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&w[i],&v[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(j>=v[i])
				f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
			else
				f[i][j]=f[i-1][j];
		}
 	return 0;
}

有限背包

P1776 宝物筛选

image.png

每次相当于求一个长度为 ss 的窗口的最大值，并且有 ww 的偏移量，这个可以通过一个单调队列来维护。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> w >> v >> s;
        memcpy(g, f, sizeof(f)); // i - 1 的状态
        for(int j = 0; j < v; j++) // 余数
        {
            int hh = 0, tt = -1; // 单调递减的单调队列
            for(int k = j; k <= m; k += v)
            {
                if(hh <= tt && q[hh] < k - s * v) hh++; // 队头超出了范围 出队
                if(hh <= tt) f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w); // 滑动窗口每移动一点就有 w 的偏移量
                while(hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt--; // 弹出比它小的队尾
                q[++tt] = k; // 下标
            }
        }
    }
    cout << f[m] << endl;
}

与无穷背包相比，每个物品选取次数有一个上限。

老样子我们可以通过枚举第三维来解决，或者加维来做无穷背包怎么优化呢？

那就可以把这些不同种物品全部摊开，变成一个一个的物品，这样就变成01背包了。

但这样还是 O(n3)O(n^3) 的，我希望物品总数变少，可以把物品少拆一点，使得这个拆分满足选取若干数加起来可以等于 0∼k0\sim{k} 中的任何一个数。

这样不管选多少个物品都可以通过拆分的这些数组合得到。

image.png

比如这样，这样就可以把任何一个数拆分成 lognlogn 个数，这样就把复杂度优化为 O(n2logn)O(n^2logn)。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;

int n, c;
int w[N], v[N], m[N];
int f[N];
int cnt;
int nw[N], nv[N];

int main()
{
    scanf("%d%d", &n, &c);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &v[i], &w[i], &m[i]);
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m[i]; j <<= 1) // 二进制拆分 将物品数降为 log 级别 即可自由组合出全部放方案
        {
            m[i] -= j;
            nw[++cnt] = w[i] * j;
            nv[cnt] = v[i] * j;
        }
        if(m[i])
        {
            nw[++cnt] = w[i] * m[i];
            nv[cnt] = v[i] * m[i];
        }
    }
    for(int i = 1; i <= cnt; i++)
        for(int j = c; j >= nw[i]; j--)
        {
            f[j] = max(f[j], f[j - nw[i]] + nv[i]);
        }
    cout << f[c] << endl;
    return 0;
}

限制背包

nn 个物品，mm 体积的背包， kk 次询问，每次强制有一个物品不能选，问最大价值。
n≤105,m≤100,k≤1000n\le{10^5},m\le{100},k\le{1000}

我们注意 mm 很小，这是一个切入点。

先正常 DP 一遍，fi,jf_{i,j} 表示前 ii 个物品用了 jj 的体积的最大价值。

再进行一次 DP，gi,jg_{i,j} 代表 i∼ni\sim{n} 已经考虑完了用了 jj 的体积的最大价值。

所以查询 p1p_1 时，枚举体积 a,ba,b ，答案就是 fp1−1,a+gp1+1,bf_{p_1-1,a}+g_{p_1+1,b}。

当前也可以分别维护一个前缀最大值，这查询的时候只需要枚举一个变量即可，如 a,m−aa,m-a。

背包 DP 的本质是不断往里加物品，在加物品的 DP 里考虑删物品很不好做，那不如分为两段累加。

分组背包

分组背包，通俗的讲就是，给你NN组物品，然后每一组你至多选择一个物品(也可以不选),每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大。

那么就可以给它们编号了，然后定义一个数组来存储第ii组第jj个的编号，然后正常存储价值、重量等。

枚举时，第一维是组数，第二维是背包容量（从大到小），第三维是第ii组的物品数，然后判断下是否能转移。

f[j]=max(f[j],f[j-w[p[i][k]]]+v[p[i][k]]);

习题：

HDU1712

#include<bits/stdc++.h>
using namespace std;
const int N=13505;
const int M=1007;
int n,m;
int x,w[N],v[N],f[N],p[M][M],c[N];
int main()
{       /*编号做法仿照P1757*/
    /*
    while(cin>>n>>m)
    {
        if(!n&&!m) break;
        int cnt=0;
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        memset(f,0,sizeof(f));
        memset(c,0,sizeof(c));
        memset(p,0,sizeof(p));
        for(int i=1;i<=n;i++)//背包种数
            for(int j=1;j<=m;j++)//物品编号
                scanf("%d",&v[++cnt]),w[cnt]=j,p[i][++c[i]]=cnt;//记录第几组第几个的编号为i
        for(int i=1;i<=n;i++)
            for(int j=m;j>=0;j--)
                for(int k=1;k<=c[i];k++)
                    if(j>=w[p[i][k]])
                        f[j]=max(f[j],f[j-w[p[i][k]]]+v[p[i][k]]);
        cout<<f[m]<<'\n';
    }
    */
    while(1)//可以改成while(cin>>n>>m)
    {
        cin>>n>>m;
        if(!n&&!m) break;
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&p[i][j]);//这里的p代表在i课程花j天学习所获得的价值
        for(int i=1;i<=n;i++)//枚举组数
            for(int j=m;j>=0;j--)//枚举背包体积
                for(int k=1;k<=m;k++)//枚举每组的物体
                    if(j>=k)//第k号物体的体积为k
                        f[j]=max(f[j],f[j-k]+p[i][k]);
        cout<<f[m]<<'\n';
    }   
    return 0;
}

混合背包

A7

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int v, w, s;
        cin >> v >> w >> s;
        if(s == 0) // 完全
        {
            for(int j = v; j <= m; j++)
                f[j] = max(f[j], f[j - v] + w);
        }
        else
        {
            if(s == -1) s = 1;
            for(int k = 1; k <= s; k <<= 1) // 二进制优化
            {
                for(int j = m; j >= k * v; j--)
                    f[j] = max(f[j], f[j - k * v] + k * w);
                s -= k;
            }
            if(s) // 剩余
            {
                for(int j = m; j >= s * v; j--)
                    f[j] = max(f[j], f[j - s * v] + s * w);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

依赖背包

A10

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

struct Edge
{
    int nxt, to;
}e[N];

int n, m, cnt;
int v[N], w[N];
int fir[N];
int f[N][N];

void add(int u, int v)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    fir[u] = cnt;
}
void dfs(int u)
{
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int vv = e[i].to;
        dfs(vv);
        for(int j = m - v[u]; j >= 0; j--) // 根节点必选
            for(int k = 0; k <= j; k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[vv][k]);
    }
    for(int i = m; i >= v[u]; i--) f[u][i] = f[u][i - v[u]] + w[u];
    for(int i = 0; i < v[u]; i++) f[u][i] = 0;
}

int main()
{
    cin >> n >> m;
    int root;
    for(int i = 1; i <= n; i++)
    {
        int p;
        cin >> v[i] >> w[i] >> p;
        if(p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    cout << f[root][m] << endl; // 跟节点的子树体积不超过 m 的最大价值
}

能量石问题

分析方法类似国王游戏。

A734

吃第 ii 块花费的时间是 sis_i 秒，当时它的价值是 Ei′E'_i，每秒它将失去 LiL_i 的价值。

那么我们在吃 ii 和 i+1i+1 的时候，考虑顺序。

假如先吃 ii，那么得到的价值就是 Ei′+Ei+1′−si×Li+1E'_i+E'_{i+1}-s_i\times{L_{i+1}}

假如先吃 i+1i + 1，那么得到的价值就是 Ei′+Ei+1′−si+1×LiE'_i+E'_{i+1}-s_{i+1}\times{L_i}

我们发现只有最后一项不同。

假如先吃 ii 更优，那么就说明 si×Li+1<si+1×Lis_i\times{L_{i+1}}<s_{i+1}\times{L_i}

所以我们可以按照 siLi\frac{s_i}{L_i} 从小到大排序，依次选即可。

  • 状态表示
    • fi,jf_{i,j}
    • 集合：所有只从前 ii 块能量石中选，且总体积（花费的时间）恰好是 jj 的方案
    • 属性：最大值
  • 状态计算
    • fi,j=max(fi−1,j,fi−1,j−si+Ei−(j−si)×Li)f_{i,j}=max(f_{i-1,j},f_{i-1,j-s_i}+E_i-(j-s_i)\times{L_i})

注意这里由于要通过当前时间来计算能量石损耗了多少能量，所以我们的 jj 记录的是恰好为当前时间的状态。

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int n;
struct Stone
{
    int s, e, l;
    bool operator < (const Stone &t) const
    {
        return s * t.l < t.s * l;
    }
}stone[N];

int f[N];


int main()
{
    int t;
    cin >> t;
    for(int C = 1; C <= t; C++)
    {
        int m = 0;
        cin >> n;
        for(int i = 0; i < n; i++)
        {
            int s, e, l;
            cin >> s >> e >> l;
            m += s;
            stone[i] = {s, e, l};
        }
        sort(stone, stone + n);
        memset(f, 0xc0, sizeof(f)); // 负无穷
        f[0] = 0;
        for(int i = 0; i < n; i++)
        {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;
            for(int j = m; j >= s; j--)
            {
                f[j] = max(f[j], f[j - s] + e - (j - s) * l);
            }
        }
        int res = 0;
        for(int i = 0; i <= m; i++) res = max(res, f[i]);
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}

状态机模型

描述的是一个过程而非结果。

把点扩展成了一个过程。

A1049

fif_i 表示抢劫前 ii 家店铺的最大收益。

正常转移：fi=max⁡(fi−1,fi−2+wi)f_i=\max(f_{i-1},f_{i-2}+w_i)

状态机分析：

先拆解状态为：fi,0,fi,1f_{i,0},f_{i,1} 表示未选最后一个店铺和选择最后一个店铺。

那么这个状态机最后的转移状态如图：

image.png|300

每一步对应一个状态，会清晰很多。

状态机还对应着一个入口的概念，也就是初始化。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 8, INF = 0x3f3f3f3f;

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

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        f[0][0] = 0, f[0][1] = -INF; // 入口 不可能选第 0 家店铺 所以设为不合法
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &w[i]);
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }
        cout << max(f[n][0], f[n][1]) << endl;
    }
    return 0;
}

A1057

对于股票对应两个过程：手中有货，手中无货。

image.png|300

  • 状态表示：
    • fi,j,0,fi,j,1f_{i, j, 0}, f_{i, j, 1}
    • 集合：过完了前 ii 天，进行了 jj 次交易，并且手中没有/有股票的状态。
    • 假如手中有股票，那么就是处于第 jj 次交易。
  • 状态计算：
    • fi,j,0=max⁡(fi−1,j,0,fi−1,j,1+wi)f_{i,j,0}=\max(f_{i-1,j,0},f_{i-1,j,1}+w_i)
    • fi,j,1=max⁡(fi−1,j,1,fi−1,j−1,0−wi)f_{i,j,1}=\max(f_{i-1,j,1},f_{i-1,j-1,0}-w_i)
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 110;

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    memset(f, 0xc0, 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 i = 1; i <= m; i++)
        res = max(res, f[n][i][0]); // 完整的交易结束 此时手里无货
    cout << res << endl;
    return 0;
}

A1058

  • 状态表示
    • 手中有货/手中无货的第一天/手中无货的非第一天。
    • image.png|500
    • 入口：手中无货的非第一天。
    • 出口：手中无货即可，那么算一个即可，但假如股票价格是单调下降的，那么最优解就是一次也不买，出口就是入口。
    • 注意本题无交易次数。
  • 状态计算：
    • fi,0/1/2f_{i,0/1/2}
    • fi,0=max⁡(fi−1,0,fi−1,2−wi)f_{i,0}=\max(f_{i-1,0},f_{i-1,2}-w_i)
    • fi,1=fi−1,0+wif_{i,1}=f_{i-1,0}+w_i
    • fi,2=max⁡(fi−1,2,fi−1,1)f_{i,2}=\max(f_{i-1,2},f_{i-1,1})
  • 初始化：f0,2=0,f0,1=f0,0=−∞f_{0,2}=0,f_{0,1}=f_{0,0}=-\infty
    • 负无穷代表不合法。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;

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

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> w[i];
    f[0][0] = f[0][1] = -0x3f3f3f3f; // 手中有货和 无货的第一天
    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]);
    }
    cout << max(f[n][1], f[n][2]) << endl;
    return 0;
}

A1052

KMP 的过程中不能让它跳到最后一个状态。

每个位置有 26 条边，m+1m + 1 个状态。

  • 1:40:00 没听懂，复习 KMP 去了，等回来补听。

区间DP

结构

它是由小区间递推得到大区间的一种 DP 方式，可以先枚举长度，再枚举左端点得到右端点，也可以直接枚举左右端点。

但之间枚举左右端点要注意顺序问题，即大的左端点要先被枚举到：

for(int i = n; i >= 1; i--)
	for(int j = i; j <= n; j++)

这样可以保证枚举到的区间的子区间之前一定更新过。

不过个人还是比较习惯：

for(int len = 1; len <= n; len++)
	for(int l = 1; l + len - 1 <= n; l++)
	{
		int r = l + len - 1;
	}

合并石子

有 nn 堆石子，每次选择相邻两堆合并，合并代价为两堆石子之和，要合并为一堆，求最小代价。

它始终是连续的一段进行合并，不能进行跳跃。

所以可以设计 fl,rf_{l,r} 代表把 [l,r][l,r] 的石子合并为一堆的最小代价，答案就是 f1,nf_{1,n}。

初始化为 fi,i=0f_{i,i}=0 ，那么怎么进行转移？

最后一次合并一定是把两堆石子合并为一堆石子，所以两堆石子之间一定有一个分界点，所以就枚举一个分界点 kk ，fl,r=min⁡l≤k≤r(fl,k+fk+1,r)+suml,rf_{l,r}=\min_{l\le{k}\le{r}}(f_{l,k}+f{k+1,r})+sum_{l,r}。

区间DP的共性之一：状态有 ll 和 rr。

大区间一定是由小区间转移而来的，所以我们要先求长度较小的区间，因此不能直接枚举 l,rl,r ，要枚举区间长度。

先枚举区间长度，再枚举 l,rl,r，再枚举断点。

石子合并（弱化版）

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];
int f[1000][1000];
int sum[10000];
int main ()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i];//前缀和
	memset(f,0x3f3f3f,sizeof(f));
	for(int i=1;i<=n;i++)
		f[i][i]=0;
	for(int len=2;len<=n;len++)//当前处理长度为len的区间 
		for(int l=1,r=len;r<=n;r++,l++)//长度为r-l+1 
			for(int k=l;k<r;k++)
				f[l][r]=min(sum[r]-sum[l-1]+f[l][k]+f[k+1][r],f[l][r]);
	printf("%d",f[1][n]);
	return 0;
}

那么石子是环呢？

我们合并为一堆时，总会有一个地方是分界点，可以断环为链，枚举每一个分界点的答案即可。

石子合并

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];
int f[1000][1000];
int sum[10000];
int main ()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=n+1;i<=2*n;i++)
		a[i]=a[i-n]; 
	for(int i=1;i<=2*n;i++)
		sum[i]=sum[i-1]+a[i];
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=2*n;i++)
		f[i][i]=0;
	for(int len=2;len<=n;len++) 
		for(int l=1,r=len;r<=2*n;r++,l++)
			for(int k=l;k<r;k++)
				f[l][r]=min(sum[r]-sum[l-1]+f[l][k]+f[k+1][r],f[l][r]);
	int ans=f[1][n];
	for(int l=1,r=n;r<=2*n;l++,r++)
		ans=min(ans,f[l][r]);
	int maxn,minn;
	minn=ans;
	for(int len=2;len<=n;len++)
		for(int l=1,r=len;r<=2*n;r++,l++)
			for(int k=l;k<r;k++)
				f[l][r]=max(sum[r]-sum[l-1]+f[l][k]+f[k+1][r],f[l][r]);
	ans=f[1][n];
	for(int l=1,r=n;r<=2*n;l++,r++)
		ans=max(ans,f[l][r]);
	maxn=ans;
	printf("%d\n%d",minn,maxn);
	return 0;
}

矩阵乘法

分别有一堆矩阵 M1=a1×a2,M2=a2×a3,M3=a3×a4,⋯ ,Mn=an×an+1M_1={a_1}\times{a_2},M_2={a_2}\times{a_3},M_3={a_3}\times{a_4},\cdots,M_n={a_n}\times{a_{n+1}}。现在要把它们乘起来，两个矩阵相乘的代价，例如M1⋅M2=a1×a2×a3M_1\cdot{M_2}=a_1\times{a_2}\times{a_3}，根据矩阵的结合律，求最小代价。

类似于能量项链。

#include<bits/stdc++.h>
using namespace std;
const int N=220;
int n;
int a[N];
int f[N][N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n+1;i<=2*n;i++)
        a[i]=a[i-n];
    for(int len=2;len<=n*2;len++)
        for(int l=1,r=len;r<=n*2;l++,r++)
            for(int k=l;k<r;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+a[l]*a[k+1]*a[r+1]);
    int ans=-1;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][i+n-1]);
    printf("%d",ans);
    return 0;
}

POJ2955 最长括号匹配

从一个括号串中选出一个最长的子序列，使其满足括号匹配。

fl,rf_{l,r} 代表 [l,r][l,r] 中最多能选出多少括号满足匹配。

// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cstring>
#include<string>
using namespace std;
const int N=300;
char a[N];
int f[N][N];
string s;
int main()
{
    while(true)
    {
        scanf("%s",a);
        s=a;
        if(s=="end") return 0;
        int n=s.length();
        memset(f,0,sizeof(f));
        for(int len=2;len<=n;len++)
        {
            for(int l=0,r=len-1;r<n;l++,r++)
            {
                for(int k=l;k<r;k++)
                    f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
                if(s[l]=='('&&s[r]==')') f[l][r]=max(f[l][r],f[l+1][r-1]+2);
                if(s[l]=='['&&s[r]==']') f[l][r]=max(f[l][r],f[l+1][r-1]+2);
            }
        }
        printf("%d\n",f[0][n-1]);
    }
    return 0;
}

POJ1651 删数

image.png

还是用 fl,rf_{l,r} 表示删除区间 [l,r][l,r] （除左右端点）的总代价，答案就是 f1,nf_{1,n}。

转移呢？

删除最后一个数 kk ，拿肯定是先把 l∼kl\sim{k} 和 k∼rk\sim{r} 之间的点都删光，

枚举一个中间点，fl,r=min⁡l<k<r(fl,k+fk,r+al×ak×ar)f_{l,r}=\min_{l<k<r}(f_{l,k}+f_{k,r}+a_l\times{a_k}\times{a_r})

// #include<bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
const int N=200;
int a[N],f[N][N];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<n;i++)
        f[i][i+1]=0;
    for(int len=3;len<=n;len++)
        for(int l=1,r=len;r<=n;l++,r++)
        {
            for(int k=l+1;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
            // printf("f[%d][%d]=%d\n",l,r,f[l][r]);
        }
    printf("%d",f[1][n]);
    return 0;
}

HDU4632 回文子序列

给定一个字符串，求回文子序列的数量。

对于一个区间 [l,r][l,r] ，我在处理它的时候一定要保证它的子区间已经处理完了。

转移：fl,r=fl+1,r+fl,r−1−fl+1,r−1f_{l,r}=f_{l+1,r}+f_{l,r-1}-f_{l+1,r-1}

这就完了嘛？如果 sl=srs_l=s_r，那么就是在原来 [l,r][l,r] 的基础上又加了这么多，所以要再加上 fl+1,r−1f_{l+1,r-1}，而且两端点也形成了一个回文子序列，所以再加一。

于是总转移方程为：fl,r=fl,r−1+fl+1,r−[sl≠sr]×fl+1,r−1f_{l,r}=f_{l,r-1}+f_{l+1,r}-[s_l\not=s_r]\times{f_{l+1,r-1}}

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
const int N=1050;
int t,n;
char s[N];
int f[N][N];
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;i++)
            f[i][i]=1;
        for(int len=2;len<=n;len++)
            for(int l=1,r=len;r<=n;l++,r++)
                f[l][r]=(f[l][r-1]+f[l+1][r]-((int)(s[l]!=s[r])*(f[l+1][r-1]))+(int)(s[l]==s[r])+mod)%mod;
        printf("Case %d: %d\n",k,f[1][n]);
    }
    return 0;
}

凸多边形

image.png

一个 nn 边形是可以切成 n−2n-2 个三角形，每个三角形的权值是它的三个顶点的点权之积，求最小权值和。

三角形是通过切割得来的。

断环为链，拷贝几份，假如一个凸八边形，那么f1,9=f1,5+f5,9f_{1,9}=f_{1,5}+f_{5,9}，其中 a1=a9a_1=a_9。

fi,j=fi,k+fk,jf_{i,j}=f_{i,k}+f_{k,j}

当这个区间被划分到三个点的时候单独算一下就好了。

树形DP

始终从叶子向根节点做 DP。

在每个节点时聚合所有儿子的信息，可能需要多遍 dfs/bfs 。

点数

一个 nn 个点的树，问这个树有多少个点？

很显然是n。

考虑用树形 DP 来解决这个问题。

树形DP的第一个维度一般是 fif_i，代表以 ii 为根的子树。

在这里表示以 ii 为根的子树有多少个点。

所以我们要求的就是 f1f_1。

初始化？我们需要把所有叶子节点的子树大小初始化为 11。

初始化的一般是叶子节点

转移？由儿子向父亲转移，把所有儿子的信息合在一起。

fu=∑fv+1f_u=\sum{f_v}+1

树形 DP 的时候我们一般会进行 DFS，同时记录当前点和它的父亲。

void dfs(int u,int fa)
{
    f[u]=1;
    for(int i=fir[u];i;i=e[i].nxt)
        if(e[i].to!=fa)
        {
            dfs(e[i].to,u);
            f[u]+=f[v];
        }
}

直径

求树的直径，直径定义为树上两个最远距离的点的路径。

树的直径无非是树上的两条链，而树上的一条链我们可以怎样表示？

假设从 p1p_1 走到 p2p_2 ，那肯定是先走到它们的 lcalca 再走到另一个点。

而对于一个点我只需要向下找两条尽量长的路径，拼起来就是以这个点为拐点的最长路径，这样对每个点的最长路径取一个 maxmax 就可以了。

那么怎么对每一个点都找到这样一条最长路径呢？

求以 ii 点出发向下的最长路和次长路，分别用 fif_i 和 gig_i 来表示。

对于叶子节点，两个量都是 0。

转移？

fi=max(fpj)+1f_i=max(f_{p_j})+1，gig_i呢？，假如先走了 p3p_3 ，那么次长路就一定不能是 p3p_3 因为这样就把 i↔p3i\leftrightarrow{p_3} 走了两遍，所以 gi=second_max(fpj)+1g_i=second\_max(f_{p_j})+1

最后的答案为 max(fi+gi)max(f_i+g_i)

复杂度为 O(n)O(n)

路径

求树上所有路径长度和

fif_i 表示以 ii 为根节点的子树的路径和，叶子节点为0，转移？没法转移，因为会有跨越不同子树的路径，还要维护一个 gig_i 表示所有点到根节点的距离之和。

gp1+sizp1g_{p_1}+siz_{p_1} 就是所有点到 ii 的路径长度之和，它们到其它子树也要算上，也就是 (gp1+sizp1)×(sizi−sizp1)(g_{p_1}+siz_{p_1})\times(siz_i-siz_{p_1}) ，因为这跳路径会被算这么多次。

所以：

fi=∑j∈sonifpj+(gpj+sizpj×vali↔j)×(sizi−sizpj)f_i=\sum_{j\in{son_i}}f_{p_j}+(g_{p_j}+siz_{p_j}\times{val_{i\leftrightarrow{j}}})\times(siz_i-siz_{p_j})

但是这样太复杂了，怎么优化呢？

其实我们只需要 DP 一个东西： sizisiz_i

这个就已经足够了。

答案式：

∑i=2nsizi×n−sizi×2\sum_{i=2}^n{siz_i\times{n-siz_i}\times{2}}

刚才我们是以点的角度考虑的，不妨换一种角度，考虑每条边。

考虑有多少条路径包含了这条边，这条边的左边有一个子树，在这个子树内任意一个点出发，以这个子树外任意一点为终点，都会经过这条边，而起点和终点又可以交换，所以是这些。注意不包含根节点，因为我们实际考虑的是边的贡献。

树的最大独立集

问一个树最多能取出多少个点使得这些点都不相邻。

状态为 fi,0/1f_{i,0/1} 代表第 ii 个点选/不选时子树最大独立集的大小。

初始化的话就是对于每个叶子节点，fi,0=0,fi,1=1f_{i,0}=0,f_{i,1}=1

那么转移呢？

如果 ii 这个点选了，那么它所有的儿子都不能选，也就是：

fi,1=∑j∈sonifj,0+1f_{i,1}=\sum_{j\in{son_i}}f_{j,0}+1

不选就无所谓了

fi,0=∑j∈sonimax⁡(fj,0,fj,1)f_{i,0}=\sum_{j\in{son_i}}\max(f_{j,0},f_{j,1})

士兵

在一棵树上布置士兵，每个士兵在节点上，每个士兵可以守护与其相连的点，问最少需要多少个士兵。

第一维还是指以 ii 为根的子树，这个根节点有三种情况，一个是自己守护自己，一个是它的儿子守护它，一个是它的父亲守护它。

0−son,1−self,2−fa0-son,1-self,2-fa

对于叶子节点，fi,0=inf,fi,1=1,fi,2=0f_{i,0}=inf,f_{i,1}=1,f_{i,2}=0

转移？

fi,0=∑j∈sonifi,1=∑j∈sonimin⁡(fj,0,fj,1,fj,2)+1fi,2=∑j∈sonifj,0\begin{aligned} f_{i,0}&=\sum_{j\in{son_i}}\\ f_{i,1}&=\sum_{j\in{son_i}}\min(f_{j,0},f_{j,1},f_{j,2})+1\\ f_{i,2}&=\sum_{j\in{son_i}}f_{j,0}\\ \end{aligned}

被父亲守护时，不能被儿子守护，因为这样会重复计算，同理在计算被儿子守护时不能计算被父亲守护。

被儿子守护时，至少一个儿子要有士兵，常见技巧：聚合儿子时，需要用另外一个 DP 来维护转移。

设 gk,0/1g_{k,0/1} 代表已经考虑完了前 kk 个儿子，是否至少有一个儿子放了士兵的所得到的最小士兵数量。

转移：

gk,0=gk−1,0+fpk,0g_{k,0}=g_{k-1,0}+f_{p_k,0}

gk,1=min⁡(gk−1,0+fpk,1,gk−1,1+fpk,0,gk−1,1+fpk,1)g_{k,1}=\min(g_{k-1,0}+f_{p_k,1},g_{k-1,1}+f_{p_k,0},g_{k-1,1}+f_{p_k,1})

这个 DP 就是为了聚合转移 fi,0f_{i,0} 的。

假如 ii 有 rr 个儿子，那么 fi,0=gr,1f_{i,0}=g_{r,1}

树形DP的时候常用DP来做聚合。

依赖背包

树形背包
nn 个物品彼此组成一个树，如果想选第 ii 种物品，必须先选它的父亲，问获得的最大价值。

状态：fi,jf_{i,j} 前 ii 种物品用了 jj 的体积所得到的最大价值 →\to 在 ii 的子树中选一些物品用了 jj 的体积所能获得的最大价值。

初始化： 叶子节点 fi,0=0,fi,wi=vi,fi,j=−inff_{i,0}=0,f_{i,w_i}=v_i,f_{i,j}=-inf

转移： 聚合的时候就要再做一个背包：

gi,jg_{i,j} 代表前 ii 个儿子的子树已经用掉了 jj 的体积得到的最大价值，g0,0=0,g0,j=−infg_{0,0}=0,g_{0,j}=-inf，转移就枚举一下第 ii 个儿子用掉了多少个体积：

gi,j=max⁡0≤k≤j(gi−1,j−k+fi,k)g_{i,j}=\max_{0\le{k}\le{j}}(g_{i-1,j-k}+f_{i,k})

fi,0=0,fi,j=gr,j−vi+wif_{i,0}=0,f_{i,j}=g_{r,j-v_i}+w_i

所以这是一个不断用 ff 求 gg ，再用 gg 求 ff 的做法。

复杂度为 O(n×m2)O(n\times{m^2})

选课

#include<bits/stdc++.h>
using namespace std;
const int N=305;
int n,m,edcnt;
int f[N][N];
int s[N];
int fir[N];
struct edge
{
    int to,nxt;
}e[N];
void add(int u,int v)
{
    e[++edcnt].to=v;
    e[edcnt].nxt=fir[u];
    fir[u]=edcnt;
}
void dfs(int u)
{
    for(int i=fir[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        dfs(v);
        for(int j=m+1;j>=1;j--)
            for(int k=0;k<j;k++)
                f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%d%d",&k,&s[i]);
        f[i][1]=s[i];
        add(k,i);
    }
    dfs(0);
    printf("%d",f[0][m+1]);
    return 0;
}

数位DP

DP 方式

参考文章
迭代 or 记搜？

记搜！

不要写迭代，又难想又难调。

常用形参：

  • pospos 代表当前枚举到的位置，

  • limitlimit 代表当前这位所受限制（true 有限制，false 无限制）

  • ansans 记录前 ii 位的答案。

设状态 fpos,sumf_{pos,sum} 代表位置 [pos+1,len][pos+1,len] 已经填完了，这些数位之和在 sumsum 的情况下，数位 [1,pos][1,pos] 无 limitlimit 的情况下，所有数的数位之和。

  • lastlast 记录上一位选的数，通常是为了限制当前位。
  • leadlead 是否有前导零。
  • rr 余数
  • stst 状态压缩

一般递归树中只有叶子节点存储的是该节点状态的答案，其它节点都是累加了它以及它子树的状态的答案。

而且初始状态已经以形参的形式传入到函数当中，无需费心初始化。

dp\text{dp} 数组的下标表示的是一种状态，独一无二的状态，一个状态是否要记录取决于它是否足够特殊，是否对答案有影响。

而有限制和无限制对应的状态又不同，因此当限制对答案数会产生影响时，要先判断没有限制，再记忆答案。

如何判断记忆化的值能否复用？

看下每次递归，影响答案的参数是否有改变？

是否是在非限制条件下记录的答案？

是否是在没有前导零的条件下记录的答案？

是否模数不同？

都要考虑。

数的个数

举个例子：给你两个整数 l,rl,r，问 [l,r][l,r] 有多少个数，显然答案是 r−l+1r-l+1 ，那么怎么用数位DP来解决，数位DP的特征一般为 [l,r][l,r] 中满足某种条件的数有多少个。

那就可以转化为 [0,r][0,r] 中满足条件的数的个数减去 [0,l−1][0,l-1] 之间满足条件的数。

所以我们就是询问 [0,x][0,x] 这段区间内有多少个数了。

把 xx 的每一位 xix_i 都写下来，最高位为 kk。

我现在要找 yy 满足 0≤y≤x0\le{y}\le{x}，把 yy 的每一位 yiy_i 也写下来，

也就是 yiy_i 有多少种方案使得每一位的 y≤xy\le x ，所以就从高位往低位依次去填，

状态 fi,0/1f_{i,0/1} 代表从高到低填到第 ii 位了当前已经填的这些位是等于 xx 的这些位还是小于 xx 的这些位，这种情况下的方案数。

其中，0→<,1→=0\to<,1\to=

初始化 fk+1,1=1f_{k+1,1}=1，第k+1k+1 位两个数都是零，所以两数相等。

转移：

fi−1,0+=fi,0×10f_{i-1,0}+=f_{i,0}\times{10}

因为高位已经小于了，所以再往低一位填 0∼90\sim{9} 都可以，所以就是乘十。

for(int j=0;j<=x[i-1];j++)
	f[i-1][x[i-1]==j]+=f[i][1]; // 如果这一位还相等，那么就转移后还想等，否则填完后就是小于。

最后的答案就是 f1,0+f1,1f_{1,0}+f_{1,1} 代表 0∼x0\sim{x} 小于等于 xx 的数的个数。

数位DP很常用一个前缀和优化。

状态设计常用 fi,jf_{i,j}，ii 表示填到第 ii 位了，jj 通常表示条件是否满足，以此决定下一位能填的数是多少，初始化就要保证两个数都没开始填的方案为 11，转移就枚举下一位填什么数。

数位之和

求一个 [l,r][l,r] 每个数每一位加起来的结果。

先转为前缀和：[0,x][0,x]

还是老状态 gi,0/1g_{i,0/1} 值便为此时的数位之和，在你填下一位的时候，要考虑当前有多少个数，而数位之和就会多出这么多倍，所以我还要维护这样的数有多少个，把上一个题的 fi,jf_{i,j} 代表这样的数有多少个。

转移和上面是同样的，只不过要加上当前填的数能填多少个 +=x×fi,j+=x\times{f_{i,j}}，xx为当前位置填的数。

g[i-1][j&&(r==y[i-1])]+=g[i][j]+f[i][j]*r;

gg 代表数位之和。

合并一下：

for(int i=k+1;i>=2;i--)//第i位已经填好了，要填的是第i-1位
	for(int j=0;j<=1;j++)
		for(int r=0;r<=9;r++)
		{
			if(j==1&&r>y[i-1]) continue;//break;// 不用转移，因为假如相等后再有一个大于 x 的数，那么这整个数就更大了
			f[i-1][j&&(r==y[i-1])]+=f[i][j]; // 都满足才相等
			g[i-1][j&&(r==y[i-1])]+=g[i][j]+f[i][j]*r;
		}

答案就是 g1,0+g1,1g_{1,0}+g_{1,1}。

差二

求 [l,r][l,r] 之间满足相邻两个数之间差至少为 22 的数有多少个

题目加了一个条件，很自然的想法就是再加一个维度，并且这个维度必然会影响我的转移，不然有啥价值。

设 fi,j,kf_{i,j,k} 前两维都一样，第三维记录了 ii 这一位填什么。

填第 i−1i-1 位的时候，使得 r−k≥2r-k\ge{2} 就可以了。

P2657

注：而这个题还需要处理前导零的情况。

回文数

求 [l,r][l,r] 之间有多少个回文数，不允许前导零存在。

设 fi,j,kf_{i,j,k} 前两维依旧相同，而找回文数的时候，我们不仅要比较高位与 xx 的大小关系，还要比较低位与 xx 的大小关系。

所以 kk 取 0,1,20,1,2 ，分别代表小于，等于，大于。

jj 代表正着填时与 xx 的大小关系，而 kk 代表对称那边与 xx 的大小关系。

因为只要前面比 xx 小，后面是可以比 xx 大的，所以可以填 22。

然后枚举一遍就可以了。

积K

求 [l,r][l,r] 之间满足各位数字之积为 KK 的数的个数，l,r,k≤1018l,r,k\le{10^{18}}。

设 fi,j,rf_{i,j,r} 代表各位数之积为 rr 的方案数，虽然开不下，但是先这么想再考虑优化。

假如使 K=111K=111，那么一定在某个位置有 3×373\times{37}，而由于是一位一位的乘，所以最后它一定只有 44 个质因子：2,3,5,72,3,5,7，因为一旦有其它质因子就直接输出无解就可以了。

所以 fi,j,a,b,c,df_{i,j,a,b,c,d} 把乘积为 rr 换成了 乘积用 2a+3b+5c+7d2^a+3^b+5^c+7^d 表示。

这个时候就可以正常进行 DP 了。

这样还没完，要考虑 KK 是否为 00，如果为 00，那么一定存在某位是 00，需要再开一维记录前 ii 位是否有 00；如果不是那么必然不存在某位为 00。

还要处理一下前导零的情况。

F

给定一个区间 [l,r][l,r]，定义函数 f(x)f(x) 代表 xx 每相邻两位差的绝对值之和，现在要在 [l,r][l,r] 之间找这样一个最大的 f(x)f(x)。

这道题还能拆成前缀和来做吗？

max⁡\max 不可以通过前缀和来做的，所以 l,rl,r 拆不开了。

定义 fi,j,kf_{i,j,k} 代表从高向低填到第 ii 位，jj 代表当前填的数与 rr 的这些位数相比是小于还是等于，kk 代表当前填的这些数与 ll 的这些位数是大于还是等于。

既然有两个限度，那就再开一维记录。

同时还要记录一下当前这位填的是什么： fi,j,k,pf_{i,j,k,p}

这样进行转移就可以了。

棋盘

在 n×mn\times{m} 的棋盘上放若干个炮使得其互相不攻击的方案数。n,m≤100n,m\le{100}

如果两个炮之间可以互相攻击，那么这一行或者这一列一定至少存在三个炮，所以每一行每一列放炮的数量就要 ≤2\le{2}。

用 fi,j,k,lf_{i,j,k,l} 代表前 ii 行已经放好炮了，有 jj 列有一个炮，有 kk 列有一个炮，有 ll 列有两个炮。

但是 j+k+l=mj+k+l=m，所以可以去除冗余变量，那就把 ll 删掉，

那么最后就是 fi,j,kf_{i,j,k} 代表这种情况下的方案数。

转移：

已经放好了前 ii 行的炮，现在要放第 i+1i+1 行的炮，

  • 放 00 个炮：fi+1,j,k+=fi,j,kf_{i+1,j,k}+=f_{i,j,k}
  • 放 11 个炮：
    • 放在有 00 个炮的列：fi+1,j−1,k+1+=fi,j,k×jf_{i+1,j-1,k+1}+=f_{i,j,k}\times{j}
    • 放在有 11 个炮的列：fi+1,j,k−1+=fi,j,k×kf_{i+1,j,k-1}+=f_{i,j,k}\times{k}
  • 放 22 个炮 ：
    • 一个放在 00 个炮的列，一个放在 11 个炮的列：fi,j−1,k+=fi,j,k×j×kf_{i,j-1,k}+=f_{i,j,k}\times{j}\times{k}
    • 两个都放在 00 个炮的列：fi+1,j−2,k+2+=fi,j,k×C(j,2)f_{i+1,j-2,k+2}+=f_{i,j,k}\times{C(j,2)}
    • 两个都放在 11 个炮的列：fi+1,j,k−2+=fi,j,k×C(k,2)f_{i+1,j,k-2}+=f_{i,j,k}\times{C(k,2)}

其实可以发现一个性质，在求方案数时，其实我们是不关心到底是怎么放的，只关心这样放会有多少种方案，所以要记录与方案有关的信息。

排列DP

这种题会告诉你有一个 1∼n1\sim{n} 的排列，求其中满足某个条件的排列有多少个。
一共有 n!n! 个排列。

逆序对

求 1∼n1\sim{n} 的排列种，逆序对数量位偶数的排列数。

答案是 n!2\frac{n!}{2}，但是怎么用DP来解？

假设这里有一个 1∼i1\sim{i} 的排列，在这里插入一个 i+1i+1，就会变成一个 1∼i+11\sim{i+1} 的排列，所以我就可以不断插入数来得到最终的排列。

设 fi,jf_{i,j} 已经处理完了所有 1∼i1\sim{i} 的排列（填到了 ii）此时逆序对数量为 jj 的方案数。

这就是排列DP常用的状态：1∼i1\sim{i} 的排列已经处理完了且满足条件数量为 jj 的方案数。

初始化： f1,0=1f_{1,0}=1

转移：枚举第 i+1i+1 个数插到哪里。有 ii 个数，i+1i+1 个位置，分别编号 0∼i0\sim{i}，那么插入到第 kk 个位置，由于我插入的是第 i+1i+1 个数，因此它比之前所有数都大，也就是说第 kk 个位置之后的数都比它小，这就是新产生的逆序对的个数 i−ki-k。

优化：只关心奇偶性，并不关心到底是多少，所以第二维模二即可。

f[1][0]=1;
    for(int i=1;i<n;i++)
        for(int j=0;j<=1;j++)
            for(int k=0;k<=i;k++)
                f[i+1][(j+i-k)%2]+=f[i][j];

排列DP不一定是从小到大或者从大到小插入，所以要根据不同情况定不同的状态，每次考虑下一个数怎么插入。

激动

对于一个排列，它的激动值维序列中严格大于前面所有数的元素的个数。
给定 nn 个数，求它们每个数的所有排列中，激动值不超过 kk 的个数。

这道题就要从大到小插入。

设 fi,jf_{i,j} 代表从大到小已经把 i∼ni\sim{n} 的数插入进来了，这个时候的激动值是 jj 的方案数。

这样每次插入的都是最小的数，无论把它插到哪里都不会影响原来的数的激动值，所以我们就只需要枚举它在哪里，只有它在最前面的时候激动值会加一，其它的时候激动值不变。

LIS

1∼n1\sim{n} 的所有排列中，LIS 不超过 2 的排列数

设 fi,jf_{i,j} 代表已经插入了 1∼i1\sim{i} 最长上升子序列的个数

假设从小到大插，插入了 1∼i1\sim{i}，下一个插入的是 i+1i+1，前面所有的最长上升子序列要么是1要么是2。

最长上升子序列长度为1，当且仅当这个序列是降序排列，特殊处理一下即可。

最长上升子序列长度为2，i+1i+1 一定不能插入到任何一个最长上升子序列的右边，所以我要插到所有长度为2的上升子序列中最左边的右端点的左边。

fi,jf_{i,j} 代表已经插完了 1∼i1\sim{i}，此时最长上升子序列最左端的右端点是 jj。

这样就可以枚举 0∼j−10\sim{j-1} 就可以了，把 i+1i+1 插进去。

  • k!=0:fi+1,j+1+=fi,jk!=0:f_{i+1,j+1}+=f_{i,j}
  • k=0:fi+1,k+=fi,jk=0:f_{i+1,k}+=f_{i,j}

状压DP

在背包问题里，考虑的顺序是对答案没有影响的。
但是会存在某些题，物品的选择顺序对答案产生影响。
比如这次获得的实际价值是这次选择的物品价值与上一个物品价值异或和，那么选择顺序就会导致答案变化，就需要一种新的DP方式——状压DP。

状压DP的暴力做法一般是 n!n! 复杂度的，比如枚举选择顺序的全排列。

设 fi,jf_{i,j} 代表上一个选的物品是 jj，第一维用一个 nn 位的二进制数（0∼n−10\sim{n-1}），这个二进制数第 xx 位代表第 xx 个物品选没选。

转移的时候看一下第 i−1i-1 位有没有选，没选我才能选上。

用二进制数代表物品选没选过，这个技巧叫做状态压缩。

还要考虑体积：当前用了 kk 的体积。

fi,j,kf_{i,j,k} 代表选了哪些，上一个选的是 jj，当前用了 kk 的体积所得到的最大价值，转移时考虑下一个选什么，编号 0≤r≤n0\le{r}\le{n}。

选这个物品的条件是((i>>r)&1)=0((i>>r)\&1)=0

fi∣(1<<r),r,k+vr=fi,j,k+wj⊕wrf_{i|(1<<r),r,k+v_r}=f_{i,j,k}+w_j\oplus{w_r}

i∣(1<<r)i|(1<<r) 相当于把 ii 的第 rr 位赋为 1。

复杂度：

O(2n×n2×m)O(2^n\times{n^2}\times{m})

这个范围一般是 n∈18∼22n\in{18\sim{22}}

棋盘式（基于连通性）

A1064

  • 状态表示
    • fi,j,sf_{i,j,s}
    • 集合：所有只摆在前 ii 行，已经摆了 jj 个国王，且第 ii 行摆放的状态是 ss 的集合。
    • 属性：方案数。
  • 状态计算
    • 已经摆完前 ii 排，且第 ii 排的状态是 aa，第 i−1i - 1 排的状态是 bb，已经摆了 jj 个国王的所有方案。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 12, M = 1 << 10, K = 110;
typedef long long LL;

int n, m;
vector<int> state;
int id[M];
vector<int> head[M];
int cnt[M];
LL f[N][K][M];

bool check(int state)
{
    for (int i = 0; i < n; i++)
        if (((state >> i) & 1) && (state >> (i + 1)) & 1)
            return false;
    return true;
}
int count(int state)
{
    int res = 0;
    for (int i = 0; i < n; i++) res += (state >> i) & 1;
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < (1 << n); i++)
        if (check(i))
        {
            state.push_back(i);
            id[i] = state.size() - 1;
            // cnt[i] = count(i);
            cnt[i] = __builtin_popcount(i);
        }
    for (int i = 0; i < state.size(); i++)
        for (int j = 0; j < state.size(); j++)
        {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b))
                head[i].push_back(j); // 可以转移的状态
        }
    f[0][0][0] = 1;
    for (int i = 1; i <= n + 1; i++)
        for (int j = 0; j <= m; j++)
            for (int a = 0; a < state.size(); a++)
                for (int b : head[a])
                {
                    int c = cnt[state[a]];
                    if(j >= c)
                    {
                        f[i][j][a] += f[i - 1][j - c][b];
                    }
                }
    cout << f[n + 1][m][0] << endl;
    return 0;
}

A327

集合式

旅行商问题（TSP）

平面内有 nn 个点，问从 11 号点出发把所有点都走一遍回到自己的最短路径。

除了一号点，其它的点没有必要走两次。

设 fi,jf_{i,j} 代表哪些点走过了，最后停留在 jj 号点的最短路径。

初始化为 f1,0=0f_{1,0}=0，把编号改为 0∼n−10\sim{n-1}。

然后枚举一个 kk，表示最后停在 jj，这一步是从 jj 走到 kk。

所以 fi∣(1<<k),k=min⁡(fi,j+disj,k)f_{i|(1<<k),k}=\min(f_{i,j}+dis_{j,k})

博弈DP

上一页
2024-03-13 12:16:51 # OI # Note
下一页