动态规划选讲

Treap_Kongzs · 2024-08-01 22:33:38 · 算法·理论

省流：本篇专供冲击NOIP一等的人使用，坐标HN

洛谷有配套题单，quite good.

若无特殊说明，本文章所有题均可在洛谷对应题型官方题单里找到

我觉得动态规划这种算法类型的知识点，就是讲题目才靠谱，空讲就几个名词，听一百遍也不会做题。所以除“楔子”部分外，一般各部分前面都不会有“通法”的讲解，而是从具体题目入手，最后能总结就总结，从而变成一篇大型题解集合（汗）

1.楔子

网上有个博主讲的比较好，DP解决的就是三个问题

最值
方案数
是否可行

对于第1、3种目的，例子是显然的，比如说最短路，我们知道spfa和dijkstra都是贪心思想，而floyd就是DP，显然属于求最值。而它的变种——传递闭包，也就是判断两点之间是否相连，就是求可行性的。

对于第二种，虽然DP的题目里比较多，但其他知识点很少有这种例子，我知道有“图的计数”这种东西，但是求方案数似乎并不是其他知识点的追求。比如说，你可以用背包DP把方案数求出来，然后写ST表（线段树？这是静态的，SGT还是太麻烦了）处理询问（比如说某个范围的最值/和），但很显然，别的数据ST表也能处理，所以ST表不是求方案数的。

闲话少叙，DP中，两个比较重要的东西就是 “阶段” 和 “决策”，就像搜索一样，程序处在一个地方，体现在变量取了什么值，这就是“阶段”；此时我们可以往哪几个方向搜，这就是“决策”。DP实质上就是通过当前的可选决策（在地图边缘就不可能往地图外面走了），选择一个，走向下一个阶段，如此循环，直到处理出所有需要的“阶段”的解，然后按题目要求，给出某个“阶段”的解。所以，下个阶段的解，确实是依赖于与能够转移到它的阶段的解的，如果你曾了解过DP的几个名词，对此应该会深有感触。

现在，给出那几个名词。

重叠子问题
最优子结构
无后效性

现在对这几个名词进行一些（也许）比较形象的说明

首先，给出一个例子，请观察：

\begin{aligned} 5=1+1+1+1+1\\ 6=1+1+1+1+1+1\\ 7=1+1+1+1+1+1+1 \end{aligned}

看到了吧，我告诉你5就是这么算的，让你再算6，你还要再一个个1相加这么算吗？显然不用。同理，7的计算也不用了，你会发现，6和7的计算过程，本质上都用到了5的计算结果，换言之，计算6和7，实质上都要先计算5，显然一个朴素的dfs()在计算6和7会进行两次5的计算，这就是出现了重叠子问题。

那我们显然可以将5的结果存下来，记为dp[5]=5，显然dp[6]=dp[5]+1，dp[7]=dp[5]+1+1。

我们再考虑一个爬楼梯的问题：

从第一阶开始，每次都可以向上爬1/2阶，求爬到第n阶的最小步数。

不妨把“状态”设为第i阶的最小步数，也就是dp[i]代表第i阶的最小步数。显然只能从第n-1和第n-2阶爬到第n阶，换言之，dp[n]只与dp[n-1]和dp[n-2]有关。而且，因为爬一步步数加一，一步的代价是一个定值，不看哪个“阶段”的脸色，只要dp[n-1]和dp[n-2]都是最优的，dp[n]必然也是最优的，大家都一样混过来的，凭什么说谁优谁劣呢。

这就是“最优子结构”，只要依赖的几个子结构（你可以视为“阶段”的解）都是最优的，那么这个阶段的解也会是最优的。

你在想，确定dp[n]的时候，你需要关心dp[n-1]和dp[n-2]是怎么来的吗？dp[n-1]是一步爬得到的还是两步爬得到的，影不影响它参与dp[n]的选取？不会吧。只要转移来的“阶段”的解确定了，这个阶段的解就搞定了，不受别的因素干扰，这也叫做“无后效性”。

你们怎么那么多人都认为“无后效性”是指各个状态之间毫无关联？难绷，那怎么转移啊

就算我讲的再明白，这三个名词还是只能在题目中体会，接下来就开始吧！

值得一提，我们大多数人对于动态规划最大的痛点不是别的，而是

是吧！对于这个问题，我看到一个办法，虽然我还不是很会用，但是你们可以试试：

设计出该题的dfs()

难绷吧！！！）dfs()是从这个“状态”转移到别的符合条件的状态，而所谓“状态转移方程”是考虑这个“状态”能被哪几个“状态”转移到，那把dfs()递归写法倒过来不就行了！比如说i+1变为i-1什么的

其实我也不是很会用这个方法，但死马当活马医，你们大可试试这个方法，~~还怪有道理的嘞~~。

其实还有一个~~很搞笑的~~方法，题目里问什么，你就拿什么确定状态，然后再想办法把状态转移方程什么的搞出来，这也是一种奇技淫巧。（

试一试！

2.线性动态规划

习题2.1.1

B3637 最长上升子序列

一道经典的线性DP，但是一开始还是很头疼的。

因为题目中所要求的子序列不一定连续，所以我们不能用简单的O(n^2)爆搜把答案搞出来。那我们就得设计别的搜索策略。

我们考虑在原数组上从后往前搜，对于每个数，我们在它的前面找出一个最长的序列，它这个位置的贡献就应该是这个序列的长度+1（把它自己算上）。思路是有了，但是把它写成dfs()却异常麻烦。

那我们怎么办呢？就直接动手把它转化成DP吧！在从后往前搜时，我们遍历的每个数都作为子序列的终点，所以dp[i]就表示以第i个数为结尾的最长子序列。然后，我们在它的前面找，如果\exists j，使第j个数小于第i个数，我们就判断j是否能让以i为终点的序列更长，如果更长，就直接更改dp[i]呗！

形式化的说：

dp[i]=\max(dp[i],dp[j]+1),j\in [1,i)

因为dp[i]+1 > dp[i]恒为真，所以会导致答案被错误的覆写，所以是j<i而不是j\le i，循环时要注意。

你怎么知道以第几个数结尾子序列最长？答案应该是dp数组的最大值，而不是dp[n]。且dp[i]和答案变量（如果你用了的话）的初始值都应该为1而并非0，因为在循环中无法更改任何值（比如说题目给了个严格递减序列坑你）时，每个数都是一个子序列，我们认为每个数本身构成的子序列是符合题目单调性的，所以答案应当为1，不如初始化时就这么做。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;

int arr[maxn];
int dp[maxn];

int main()
{
    int n=0,ans=1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        dp[i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(arr[j]<arr[i])dp[i]=max(dp[i],dp[j]+1);
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

接下来还有一个常用优化技巧，就是所谓的二分查找优化

我们前面的朴素算法每扫一个数都要再扫一遍它前面的所有数，复杂度基本上是O(n^2)，显然不很优。我们怎么优化呢？

每扫一个数肯定是免不了的，那我们只能在“扫前面的数”这里做文章。而后我们就想到了二分查找，它可以让O(n)的查找变为O(\log_2 n)，整体就可以降成O(n\log_2 n)，这是一个很诱人的优化。

麻烦是二分查找需要“有序”，原数组会一定做到有序吗，答案是否定的。那我们怎么做到有序呢？有人就想了个好办法：

新建一个副本数组，然后把它的第一个元素设为原数组的第一个元素，后面就开始操作。

对于原数组的第i个数，我们判断：

如果第i个数比副本数组的最后一个数大，那它就能使子序列变长，我们就把第i个数加进副本数组的末尾。

如果反之，我们就把副本数组中第一个大于等于它的数改成它，“大于等于”显然就要用二分查找，如果你想用STL，记得要用lower bound。

当所有数都遍历完后，副本数组的长度就是答案。为什么？

首先要明确一点，副本数组一定是有序的，因为你加进去的数一定比原来的最后一个元素都大，所以一定是递增的。

“反之”部分的操作，是让副本数组里的元素尽可能地小，为什么？因为要塞下更多的数。前面的数小了，后面的数才小得下来，这样，因为使所有的数都最小了，最末尾的数也一定是最小的，这样能够新加数进来的概率就大些。

这样，我们就从一个无序的数组里抠出一个最大的有序数组，那它的长度显然就是最优的答案。

扫n个数，每次判断操作O(1)，就算每个数都要加进去，每次也只有O(\log_2 n)，所以总时间复杂度就是O(n\log_2 n)

但是有一点需要注意，如果要求输出方案，副本数组并不是最优解，我们不予证明。如果需要，你应该再开一个数组表示每个点的前驱（在达成最优解的序列中，这个数前面应是哪个数），然后在找答案时找到以哪个数结尾最优，以前驱不为空为终止条件循环输出。

啊，好像这个优化其实是另一种算法，没别的，我的dp数组从头到尾都没出现过……

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;

int arr[maxn];
int brr[maxn];//二分优化数组
int dp[maxn];

int main()
{
    int n=0,ans=1;
    cin>>n;
    arr[0]=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        dp[i]=1;
    }
    brr[1]=arr[1];
    for(int i=2;i<=n;i++)
    {
        if(arr[i]>brr[ans])
        {
            brr[++ans]=arr[i];
        }
        else
        {
            int j=lower_bound(brr+1,brr+ans+1,arr[i])-brr;
            brr[j]=arr[i];
        }
    }
    cout<<ans;
    return 0;
}

习题2.1.2

P1004 [NOIP2000提高组] 方格取数

~~比较无语的一个题~~

我们当然可以两遍dfs()，第一遍把走过的格子都置零，然后第二遍就不受干扰了。但是\color{#052242}{TLE}似乎在前方等着你。

然后我们就想到用dfs()来反推DP状态的快捷方法，我们dfs()中虽然只用到了x和y两个自变量，但由于我们走了两遍，DP状态似乎变成四维的更好

所以，我们设dp[i][j][k][l]表示第一次从(1,1)走到(i,j)这一格，第二次从(1,1)走到(k,l)这一格的最优解。显然答案为dp[n][n][n][n]，~~怎么又是奇技淫巧~~

显然有四种决策：

第一次从上面过来，第二次从上面过来，dp[i][j][k][l]=dp[i][j-1][k][l-1]
第一次从左边过来，第二次从左边过来，dp[i][j][k][l]=dp[i-1][j][k-1][l]
第一次从上面过来，第二次从左边过来，dp[i][j][k][l]=dp[i][j-1][k-1][l]
第一次从左边过来，第二次从上面过来，dp[i][j][k][l]=dp[i-1][j][k][l-1]

就这四种了，你显然不可能同时走下和走右，所以i和j，k和l不可能同时更改。

所以，我们就从这四个状态中取最大值，然后加上两次取到的数，dp[i][j][k][l]就确定了！再回想一下是不是！

然后，你的样例输出了72......

CaO，so why

因为若统计的是两次走到同一格时，你就会发现，这一格的数你捡了两遍！显然是要不得的！

那怎么办？从原数组中置零？别的地方转移要用怎么办？！（慌）

你傻啊，这里的数据又没有特殊处理，捡了两遍，你去掉一个就是了。（乐）

也就是说，当i==k且j==l时，我们减掉一份当前格子的数。这样就解决了。

讨论区有人说要把n开到200或300，为了把dfs()卡过去，我在心里是支持的。（

AC Code：

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

int graph[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];

int main()
{
    int n=0,x=1,y=1,val=1;
    cin>>n;
    while(1)
    {
        cin>>x>>y>>val;
        if(x==0&&y==0&&val==0)
        {
            break;
        }
        graph[x][y]=val;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            for(int k=1;k<=9;k++)
            {
                for(int l=1;l<=9;l++)
                {
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]),max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+graph[i][j]+graph[k][l];
                    if(k==i&&l==j)dp[i][j][k][l]-=graph[i][j];
                }
            }
        }
    }
    cout<<dp[n][n][n][n];
    return 0;
}

但是大概不用另出别的题了，这道题也许就可以卡掉。

习题2.1.3

P1006 [NOIP2008提高组] 传纸条

几乎是双倍经验好吧。以下直接给出改动部分：

输入更友好，直接改成读入m \times n的矩阵就可以了
同理，i和k的最大值也要改成m，不然就不符题目地图了。汗
又同理，最终的输出是两次到达(m,n)这个点，所以我们要输出dp[m][n][m][n]，而不是~~形式简洁，充满魅力的dp[n][n][n][n]，爱来自P1004~~

关于这题为什么可以用方格取数的代码做，这是个好问题，我们不做证明。事实上，两条路径是否能相交这个问题众说纷纭，我们~~这种蒟蒻~~就不管了。:-)

AC Code：

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

int graph[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];

int main()
{
    int n=0,m=0;
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>graph[i][j];
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            {
                for(int l=1;l<=n;l++)
                {
                    dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i][j-1][k][l-1]),max(dp[i-1][j][k][l-1],dp[i][j-1][k-1][l]))+graph[i][j]+graph[k][l];
                    if(k==i&&l==j)dp[i][j][k][l]-=graph[i][j];
                }
            }
        }
    }
    cout<<dp[m][n][m][n];
    return 0;
}

3.背包动态规划

习题3.1.2

P1802 5 倍经验日

还是比较板的0-1背包，讨论区有个远古帖子说是完全背包，这个不太现实。

我们考虑0-1背包的经典状态，设dp[j]表示恰好用了j个药的最大经验。

现在来思考决策：

对于第i个对手，第j个药

打赢这个对手，用掉use_i个药，所以dp[j]=dp[j-use[i]]+win[i]
输了，按题目说是会浪费药，但你傻啊，数据都摆在这里，是公平博弈（？），明知会输，你还用药干什么？白嫖经验不香吗？dp[j]=dp[j]+lose[i]
不讲武德，先撤为敬，传统功夫讲究点到为止。dp[j]=dp[j]

显然第三种是完全对答案没有贡献的、只会拖你运行时间的，那我们就不写了！:-)

我们还可以搞点剪枝，如果j小于use_i，那肯定打不过，我们就直接给dp[j]+=lose[i]，直接“我说婷婷，当时眼泪就流下来了”，其实是怕数组下标越界，\color{#9D3DCF}{发生RE}

至于为什么是+=，这是个好问题，给出一组数据：

2 1
1 9 1
1 1 4

我们显然可以干掉第一个对手，然后拿9，对第二个人认输，再拿1，答案应为10，最终答案为50。

但是，如果不用+=而用=，在对第二个人的判断时，就会覆盖掉前面可能打赢的经验，从而出错。

诶，这个数字不是很完整，臭就臭吧，只臭一半几个意思？[doge]

因为另一半不满足题意。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
#define ll long long

ll wins[maxn];
ll loses[maxn];
ll costs[maxn];
ll dp[maxn];

int main()
{
    int n=0,m=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>loses[i]>>wins[i]>>costs[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            if(j>=costs[i])
            {
                dp[j]=max(dp[j]+loses[i],dp[j-costs[i]]+wins[i]);
            }
            else dp[j]+=loses[i];
        }
    }
    cout<<5*dp[m];
    return 0;
}

2.3 有依赖的0-1背包

这种题型就来源于下面的习题，在这种题目中，可选物品分为“主件”和“附件”两种，要买附件，必须先买主件，其余条件和0-1背包相同。

网上面的教程大多把它和分组背包联系起来，~~但我都没打算写分组背包~~，所以要另辟蹊径。

当无法解决问题时，~~先尝试简化问题~~。我们假设：

没有一个附件有多个主件
主件不会依赖自己的某个附件

这下可能有一个策略，我们可不可以主件和主件一起选，附件和附件一起选呢？不属于同一个主件的附件显然互不干扰，都是凭指标被选上，所以不考虑他们的冲突。同理可得主件之间也不会有冲突，事实上，我们的痛点是怎么搭配主件及其附件。

我们可以考虑，先决定主件买不买，因为没主件显然不能买附件。我们直接把不买的主件剪掉。然后一个个枚举主件和附件的搭配，决定最终dp[i]的赋值。每个枚举的内部显然就是0-1背包了。

注意到整个数据中主件和附件的关系都是一棵树，所以状态点过多导致枚举破坏马蜂时，可以尝试写成树形DP~~我还没讲~~。我们所做的，就是在若干棵以主件为根的树的森林中，决定每棵树的节点选取方案。~~搞不好你建个超级点就变成真正的树形DP了~~

习题2.3.1

P1064 [NOIP2006提高组] 金明的预算方案

这个题就是~~罪恶之源~~，没什么好讲的。

注意到题目的数据给出了附件数量的限制，显然可以枚情况，只有四种。

不买附件
买第一个附件
买第二个附件
买两个附件
不买主件（剪了）

我们可以定义个结构体，存每个物品的相关信息，最重要的是id和belong，如果物品是主件，id定为自己的编号，belong设为0就可以了，是附件的话，id定为主件的，belong是主件现有附件数目+1（可以开个数组存着），然后以id、belong关键字顺序排序，主件的两个附件（如果有）就可以表示成i+1，i+2了，很方便吧。

怎么判断从属关系呢？id相等就行了吧！

钱不够就跳了，不要数组越界。

动手！！！

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=3.2e4+5;

struct goods
{
    int id;
    int val;
    int contirbution;
    int belong;//0-主件，1-第一附件，2-第二附件
};
goods arr[maxn];
int belongnum[maxn];
int dp[maxn];

bool operator<(goods a,goods b)
{
    if(a.id==b.id)return a.belong<b.belong;
    return a.id<b.id;
}

int main()
{
    int n=0,m=0,v=0,p=0,belong=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>belong;
        if(belong==0)arr[i]={i,v,v*p,0};
        else arr[i]={belong,v,v*p,++belongnum[belong]};
    }
    sort(arr+1,arr+m+1);
    for(int i=1;i<=m;i++)//先处理主件
    {
        if(arr[i].belong)continue;//附件先别管
        for(int j=n;j>=arr[i].val;j--)
        {
            dp[j]=max(dp[j],dp[j-arr[i].val]+arr[i].contirbution);
            if(arr[i+1].id==arr[i].id&&j>=arr[i].val+arr[i+1].val)//一个个枚附件购买情况
            {
                dp[j]=max(dp[j],dp[j-arr[i].val-arr[i+1].val]+arr[i].contirbution+arr[i+1].contirbution);
            }
            if(arr[i+2].id==arr[i].id&&j>=arr[i].val+arr[i+2].val)
            {
                dp[j]=max(dp[j],dp[j-arr[i].val-arr[i+2].val]+arr[i].contirbution+arr[i+2].contirbution);
            }
            if(arr[i+2].id==arr[i].id&&j>=arr[i].val+arr[i+1].val+arr[i+2].val)
            {
                dp[j]=max(dp[j],dp[j-arr[i].val-arr[i+1].val-arr[i+2].val]+arr[i].contirbution+arr[i+1].contirbution+arr[i+2].contirbution);
            }
        }
    }
    cout<<dp[n];
    return 0;
}

4.区间动态规划

习题4.1.1

P1175 石子合并（弱化版）

注意到本题相当于求第1到n堆石子合并的最小代价，我们直接想到设定一个状态：dp[i][j]表示第i到j堆石子合并的最小代价，~~奇技淫巧生效了~~。

然后怎么鼓捣出状态转移方程呢？我们再观察怎么把这个问题细分下去，然后，有一个很有趣的性质，第i和j堆石子中，有j-i-1堆石子。

这又有什么用呢？诶，你就要想到，我们可以以这几堆中间的石子作为“中转点”，因为把i和j这几堆石子合并的最优解，实质上就是在i到j之间找一堆石子k，以它为分界，将两边的石子各自合并，得到最优解，然后再加上合并最终两堆的代价就可以了！仔细想想，最终的最优解是不是只受这三个因素干扰？

所以，我们枚举每两堆石子构成的“区间”，再枚举这中间的几堆石子，看以哪堆石子为分界，两边各自的最优解和这两堆的合并代价之和最小。这个代码将是三重循环。

最终答案应为dp[1][n]，时间复杂度约为O(n^3)

AC Code：

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

int arr[maxn];
int sum[maxn];
int dp[maxn][maxn];

int main()
{
    int n=0;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        sum[i]=sum[i-1]+arr[i];
        dp[i][i]=0;
    }
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=i;k<=j-1;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

好，我们来看这个问题的标准版

习题4.1.2

P1880 [NOI1995] 石子合并

捕获NOI水题。1995年的机子，很难想象在现在根本没法用的WINDOWS 95上面跑这种题目的评测，我记得当时搞工程建win98的虚拟机，RAM开到256MB都一摞bug，只能开128MB，而题面要求居然是125MB，很难想象怎么跑。

言归正传。这道题的难点是地图是个圆，是环形的，我们要合并有点困难，主要是处理第1和n堆石子的合并有些困难（。那怎么把这个问题解决掉呢？

如果你曾在隔壁leetcode上刷过DP，应该对“打家劫舍II”感到熟悉，对于环形地图，它可以拆成arr[1]到arr[n-1]和arr[2]到arr[n]两段直线，然后在这个基础上DP，比较好写。但是它是不相邻问题，对于本题这种必相邻问题，我们该怎么搞所谓“破环成链”的技巧呢？

很抱歉，就算是拆开，每剁一刀，都会出现两个端点，统计不到它们合并是否有贡献。所以，没有一个合适的下手的地方，真的很惨。

诶，那我们都拆一遍不就行了？因为圆上的n个点，中间必定有n个空嘛。每个空剁一刀，都是一样的内容，不怕没有直线段点没有统计到合并的贡献了。

这里有一个技巧，我们只要读入原数组，然后在它屁股后面接一个一模一样的数组，这样，统计每一刀后的结果变成了统计arr[i]到arr[i+n]的结果。减小常数。

然后，我们只要以1到n的每个数作为起点，跑一遍线性的合并石子就可以了。

那是套四层循环吗？！当然不可能，~~你还想不想要洛谷的评测机了~~。所以显然不是，事实上，也只要三层循环。

最内层循环仍然是从每个子区间的的答案中找出最优解
往上走一层，线性的板子是枚举右端点，但是这里我们把它变成枚举左端点走的距离，也就是左右端点的距离，先别急啊，看下去
再往上走一层，好，这里还是枚举左端点，但从2枚举到n

为什么要这么设计呢？你可以手动模拟一下。

假设，第一、二层的循环变量为i和j，显然右端点为i+j-1，显然它应小于2n，防止越界：

j=1$，我们扫到了$[1,2],[2,3],[3,4]...
j=2$，我们扫到了$[1,3],[2,4],[3,5]

这样我们就可以实现答案的集中，因为数据为环形，所以我们用这样的话，就可以统计到所有刀对答案的可能贡献。good

因为砍了n刀，最后的答案可能在任意一个区间里，我们要重新枚一遍每个dp[i][i+n-1]，取最值输出。

最小/大值求法在DP方程思想上没有区别，只是改一个min和max的问题。

AC Code：

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

int arr[maxn];
int sum[maxn];
int dp[maxn][maxn];//最小值
int res[maxn][maxn];//最大值

int main()
{
    int n=0;
    cin>>n;
    memset(dp,0x3f,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        arr[i+n]=arr[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        sum[i]=sum[i-1]+arr[i];
        dp[i][i]=0;
        res[i][i]=0;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j+i-1<=2*n;j++)
        {
            for(int k=j;k<j+i-1;k++)
            {
                dp[j][j+i-1]=min(dp[j][j+i-1],dp[j][k]+dp[k+1][j+i-1]+sum[j+i-1]-sum[j-1]);
                res[j][j+i-1]=max(res[j][j+i-1],res[j][k]+res[k+1][j+i-1]+sum[j+i-1]-sum[j-1]);
            }
        }
    }
    int minres=0x3f3f3f3f,maxres=0xafafafaf;
    for(int i=1;i<=n;i++)
    {
        minres=min(minres,dp[i][i+n-1]);
        maxres=max(maxres,res[i][i+n-1]);
    }
    cout<<minres<<endl<<maxres;
    return 0;
}

5.树形动态规划

习题5.1.1

P1352 没有上司的舞会

直接就是树形DP的板子。

如果是下属来，上司必须来，那就是大号的金明了（

因为树形的结构很适合dfs()，所以我们考虑把它的状态转移丢到dfs()里头去处理，那么我们怎么做呢（

众所周知，DP最难的就是设计状态，现在也是如此。认真看一眼题目......睡着了(bushi)

题目是这么描述的：

邀请哪些职员可以使快乐指数最大

额，难道设dp[i]表示邀请i个人时的解？那这会是哪几个人呢，似乎8行。

我们再想想，既然决定用dfs()搞定树形DP，那我们就从树的dfs()上入手考虑

假设我们从树根搜下去，用深搜实现这个问题，会突然出现一个显然的关系式

dfs(i)=\sum^{child(i)}_{j=1}dfs(son_{ij})

终止条件为：

dfs(leafnode)=arr[leafnode]

其中chlid(i)表示i的孩子个数，son_{ij}则表示i的每个具体的孩子节点，arr[i]表示该节点的值。

你还别说，这个关系式真的很显然，而且很有用。

受此启发，我们直接将dp[i]设为在当前节点的最优解！

……

好像怪抽象的……

先别管，~~好不容易整出来的~~

我们再来思考一下决策：

节点i对应的人不来，那Ta的下属都可以来，当然也可以不来，~~坐在家里上洛谷~~。

dp[i]=\sum^{child(i)}_{j=1}dp[son_{ij}]

节点i对应的人来，那Ta的下属都不来了，~~太搞笑了~~

哦，这时的状态方程该怎么写呢……难绷

看来是时候对状态做出一些改变了！我们设dp[i][0]表示i不来的情况，设dp[i][1]表示i来的情况。状态方程就清晰了！！！

dp[i][0]=\sum^{child(i)}_{j=1} \max (dp[son_{ij}][1],dp[son_{ij}][0])

dp[i][1]=arr[i]+\sum^{child(i)}_{j=1}dp[son_{ij}][0]

看到一大摞数学公式就是爽啊！！！(bushi)

注意一个领导是不能把所有下属都赶走后自己也不来的，所以一旦i来，就先把自己的值加上！

good

注意本题领导不一定是1号~~倒反天罡~~，所以一旦是建有根树（比如说示例代码），就一定要查找哪个点只出不进或者只进不出（看你怎么确定边的方向了），以那个点作为起点！

哦，还有最后的答案，显然当所有员工都确定好了，校长来不来的最优解才能确定，换言之，校长的来不来能够代表全学校的安排已经确定。所以，我们看校长来还是不来好，然后输出校长的最优解。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e3+5;

int arr[maxn];
struct edge
{
    int to;
    int last;
};
edge edges[maxn];
int head[maxn];
int degree[maxn];
int tot=0;
int dp[maxn][2];

void dfs(int s)
{
    dp[s][1]=arr[s];
    for(int i=head[s];i!=0;i=edges[i].last)
    {
        int v=edges[i].to;
        dfs(v);
        dp[s][1]+=dp[v][0];
        dp[s][0]+=max(dp[v][0],dp[v][1]);
    }
}

inline void adde(int u,int v)
{
    edges[++tot].to=v;
    edges[tot].last=head[u];
    head[u]=tot;
    degree[v]++;
}

int main()
{
    int n=0,u=0,v=0,s=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        adde(v,u);
    }
    for(int i=1;i<=n;i++)
    {
        if(degree[i]==0)
        {
            s=i;
            break;
        }
    }
    dfs(s);
    cout<<max(dp[s][0],dp[s][1]);
    return 0;
}

动态规划选讲

省流：本篇专供冲击NOIP一等的人使用，坐标HN

1.楔子

2.线性动态规划

习题2.1.1

习题2.1.2

习题2.1.3

3.背包动态规划

习题3.1.2

2.3 有依赖的0-1背包

习题2.3.1

4.区间动态规划

习题4.1.1

习题4.1.2

5.树形动态规划

习题5.1.1

6.状态压缩动态规划