因为dp太菜所以（其实哪儿都菜

嘛这就算是每天的做dp记录啦orz

为了省篇幅有些就一句话题解了吧大概（

记住要想清楚再写

想不出怎么设计状态的时候看看数据范围

想不出怎么转移的时候想想如果写暴力是怎么写的然后从记忆化搜索入手

2.26

打算先把51nod的所有动规都做了 有一些之前就做过了就不写了

51nod1270

题意：数组A包含N个元素A1, A2……AN。数组B包含N个元素B1, B2……BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= Bi。数组A的代价定义如下：

（公式表示所有两个相邻元素的差的绝对值之和）

给出数组B，计算可能的最大代价S。

数组的长度N(1 <= N <= 50000)。数组元素Bi(1 <= Bi <= 10000)。

思路：看题目范围就知道不可能是O(N*Bi)的做法所以就肯定是取特殊值了，这里取的就是1或者Bi，dp(i)(j)表示第i个数字取最大值或者最小值的最大代价，然后状态转移就可以了。

2.27

51nod1201

题意：将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

思路：这里是不同的整数，dp的话内存和循环次数都ojbk的，因为1+2+3+…+m=n（预处理部分，确定最多几个数字相加）。

dp(i)(j)：有i个数字相加和为j的方案数。

dp(i)(j)=dp(i-1)(j-i)+dp(i)(j-i)。

dp(i-1)(j-i)：i-1个数字相加再加一个i;

dp(i)(j-i)：i个数字每个数字都加1。

本来是想01背包（恰好装满的）做的qwq就是把每个数字当成物品，选或者不选，容量为n的背包，dp(i)(j)dp(i)(j)=(dp(i-1)(j)+dp(i-1)(j-i))%MOD;这样做的 然而不对又不知道怎么错了…

顺便这里提一下恰好装满的01背包的做法，把dp初始化为-INF，其他和可不装满的01背包一样。

2.28

51nod1020

题意：给出2个数n和k，求1-n的全排列中，逆序数为k的排列有多少种？

思路：

dp(i)(j)：1-i的全排列中逆序数为j的方案数。

从题目的栗子来看：

1 2 3 4的排列中逆序为3的共有6个，分别是：1 4 3 2；2 3 4 1；2 4 1 3；3 1 4 2；3 2 1 4；4 1 2 3。

考虑123排列有1 2 3；1 3 2；2 1 3；2 3 1；3 1 2；3 2 1。

比如1 2 3可以得到逆序数为0 1 2 3的1-4排列，因为只要考虑4开头的逆序数对就可以了，所以就知道dp(i)(j)=∑dp(i-1)(k)，再考虑一下，知道kmin=max(0,j-i+1),kmax=min(j,(i-1)*(i-2)/2)。然后dp就可以了。这里直接开1000乘20000的long long数组会爆内存，所以用两行的滚动数组即可。但是这样会超时…

想到了优化，要优化肯定是从dp(i)(j-1)来入手，因为max(0,j-i+1)<=k<=min(j,(i-1)*(i-2)/2)，右边可以直接写成j，因为如果(i-1)×(i-2)/2比较小，那么这个以后肯定都是0，加了也没有什么关系；左边呢，就写成j-i+1，因为如果0比较大，那这个是负数，也可以调整，那么j-i+1<=k<=j。所以dp(i)(j)=dp(i)(j-1)+dp(i-1)(j)-dp(i-1)(j-1-i+1)=dp(i)(j-1)+dp(i-1)(j)-dp(i-1)(j-i)。考虑到j=0的情况，dp(i)(0)=1；考虑到j-i+1可能是负数，当j-i<0，最后一项不减。

注意这里是多组数据…所以预处理存下所有的dp(i)(j)就好了。

3.7

想不到立着的flag这么快就倒了qwq我觉得不行（。

51nod1154

题意：有一个字符串S，求S最少可以被划分为多少个回文串。

思路：dp[i]:前i个字母最少可以被划分为多少个回文串。

可以写写看。比如a，即dp[0]=1；当aa时，dp[1]=1，当ab时，dp[1]=dp[0]+1=2；当aba时，dp[2]=0+1=1，当abb时，dp[2]=dp[0]+1=2。由此可见，dp[i]=dp[j-1]+1(j<=i&&j到i为回文串)。

那么如何知道j到i为回文串呢？

可以继续dp预处理一下，hw(i)(j)：i到j是否是回文串，只有当中间为回文串而且a[i]==a[j]，i到j才为回文串。

3.9

一直做51nod的题有点吃不消QAQ做个记忆化搜索缓一缓w

POJ1088

题意：给一张高度图，滑雪只能往低的地方滑，求最长的一条路。

思路：很简单的记忆化搜索…没啥好说的…因为题目看错WA了一发…要审清题意啊…

HDU1428

题意：从(1,1)走到(n,n)，给出每个地点的费时，考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更快，问总路线有几条。

思路：注意四个方向都可以走，刚开始以为只往右下走，直接两次dp了，所以WA了。先处理出每一点到机房的最短路，用bfs松弛的思想，之后记忆化搜索即可。

3.11

51nod1241

题意：一个数组的元素为1至N的整数，现在要对这个数组进行排序，在排序时只能将元素放在数组的头部或尾部，问至少需要移动多少个数字，才能完成整个排序过程？

思路：只要考虑最长连续子序列即可，移动的时候，其他数字都可以按序每个数字移动一次即可，即答案为n-最长连续子序列的长度。

3.12

51nod 1636

题意：一个学年由n天组成。A学校有m门课程，每天学生必须学习一门课，一门课程必须在一天内学习完。在学习完第i门课程后，学生们会收到 xi 个家庭作业，其中 xi是区间[ai,bi]里的一个整数 。每门课还有一个属性，就是复杂度 ci 。A学校现在要制他们的课程表，具体要求如下：在课程表中，随着天数的增加，课程的复杂度是严格递增的。

除了第1天，每天的作业量必须是前一天的k倍，或者比前一天多k个作业。（假设第i天的作业量为 xi ，则对于i(1＜i≤n)到满足 xi ＝ k+xi−1 或 xi ＝ k⋅xi−1 ）；

现在，给定天数n，系数k，和m门课程的ai，bi，ci（1≤i≤m）。要求计算一个学年可以安排最大的总作业量( 总作业量的表达式是∑ni=1xi )是多少。

思路：刚开始思路被背包束缚住了，这么设计状态：dp(i)(j)(k)表示选到第i门选了j门最后一门作业量是k，但是1≤ai≤bi≤10^16，数组存不下，因为有这个条件bi-ai≤100，又想跟l可以搭上关系，但是想想却不能确定前一门是哪一门，所以这样是不行的。考虑另一种状态设计：dp(i)(j)(k)表示第i天选了第j门作业量为a[j].l+k的最大作业量，先sort一下满足dp(i)(j)(k)=max(dp(i-1)(l)(a[j].l+k-z-a[l].l),dp(i-1)(l)((a[j].l+k)/z-a[l].l))(l<j-1)。debug到意识模糊，这种三维的调试起来最麻烦…自己想样例也是很重要的啊…其实是忘了一个点，要转移还漏了一个条件，要注意转移的前一个状态要存在，并不是只要判断合理就可以了。

3.14

51nod1732

题意：给出一个字符串，求从i和从j开始的子串的最长公共前缀。

思路：dp(i)(j)：i和j的匹配度。根据样例的例子写写画画就知道有转移方程dp(i)(j)=dp(i+1)(j+1)+1，所以只要先预处理出来相同的a(i)和a(j)，然后倒着跑n^2的循环就可以了。

3.15

51nod1354

题意：给出n个数，输出当前子序列里面的所有元素乘起来恰好等于K的子序列数。

思路：很容易想到这是一个选与不选的问题，dp(i)(j):选到第i个数字乘积为j的方案数，但是这里2<=K<=100000000，所以要考虑存更小的，所以想到了可以存因数，预处理出来K的因数，map存一下，然后dp即可。这里要注意一个情况，当第一个数字为1时，dp(1)(1)应该是2，因为这可能是不选也可能是1，有两种情况。

3.16

51nod1055

题意：给出n个数，从中选出最长等差数列。

思路：这道题目想了很久然而还是gg，是看了题解做出来的qwq双指针什么的实在是没想到啊QAQ

首先想的是dp(i)(j):最后一个数为a[i]等差为j的最大长度，这样想很简单，可是就是数据存不下，而且还要考虑j的所有情况，我是开了两个map，map本来就慢，就gg了。

看了题解，发现它利用了等差数列2*a[j]=a[i]+a[k]的性质。它是这么设计状态的：dp(i)(j):第一个数为a[i]，第二个数为a[j]的最长等差数列的长度。有dp(i)(j)=dp(j)(k)+1(当满足性质时)，这么说是要O(n^3)的，但是这里很巧妙，用了双指针左右扫的方法。

这里还用了黑科技，10000*10000讲道理是开不下的，所以这里用了short int类型。

具体看代码：

int a[10010];
short int dp[10005][10005];//以a[i]和a[j]为前两个数的最长的等差数列
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            dp[i][j]=2;
    for(int j=n-1;j>=2;j--)
    {
        int i=j-1,k=j+1;
        while(i>=1&&k<=n)
        {
            if(a[i]+a[k]==2*a[j])
            {
                dp[i][j]=dp[j][k]+1;
                i--;k++;
            }
            else if(a[i]+a[k]<2*a[j])k++;
            else i--;
        }
    }
    int MAX=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(dp[i][j]>MAX)MAX=dp[i][j];
    printf("%d\n",MAX);
    return 0;
}

3.21

51nod1274

题意：给出一张无向图，求最长严格递增路径。

思路：这道题看起来很简单记忆化搜索一下就ojbk了可是我debug得真的有点难受orz不过很好自从这个一天一dp计划开始就尽量不看题解了有进步hhh

刚开始想的是从每个点的最长路径入手，可是考虑到这和前一条边的长度有关系，所以就考虑dp(i):从i条边开始的最长路径。这里，我又没考虑周全，我直接把每条无向边当成一条边了，然后我还存了每条边的两个端点，然后再两个方向dfs，然而这是有问题的，因为会存在是从这个端点进入但是又从这个端点出的问题，我debug的时候模拟样例真的几乎要受不了了orz所以才要考虑把一条无向边当成两条有向边来存…这样就不会存在这种问题了…这样记忆化搜索写起来也很简单了…

哎这道题我写了好几个版本QAQ又一直纠错就很难受qwq

总结一点吧 一定要把所有细节都考虑好再写 否则debug的话心态会炸QAQ还有实在不行的时候 就一定要全部推翻重写 真的！

3.25

CodeForces934C

题意：给出一个只有1和2的串，允许翻转一个区间[l,r]，求翻转后最长的非递减子序列长度。

思路：很容易看出来是dp的题目但是题目看错真是要命QAQ以为是子串所以想着要求每个区间最左边/中间/右边连续最长非递减长度 想着这难道要区间合并什么的嘛QAQ然而 题目不是这样的 subsequence是子序列的意思 substring才是子串

因为数字只会出现1和2，所以把这个数列可以分成三部分，左部分找1的最长子序列，右部分找2的最长子序列，中间部分因为是翻转的，所以就找最长非递增子序列，枚举左右端点dp即可。

dp(i)(j)(k):[i,j]中以k结尾的最长非递增序列长度。

转移一下就可以了。

3.29

51nod1052

题意：N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。

思路：考虑dp(i)(j)：前i个数被分为j段的最大和（包括第i个数）。

可以知道有两种转移，一种是加在前一段里面，即dp(i-1)(j)+a[i]，还有一种是当成另外一段，即dp(k)(j-1)+a[j] (k<i)。

所以dp(i)(j)=max(dp(i-1)(j)+a[i],max(dp(k)(j-1)+a[j])(k<i))。

这里k遍历的话n^3会超时，所以要开个数组pre(j-1)来记录之前的所有dp(k)(j-1)，所以这个内层循环应该倒着来。

3.30

做dp每次看到AC的时候就感觉好开心hhh（毕竟都是自己做的

不过每次写debug得有点多 注意写的时候要仔细啊

51nod1503

题意：刚开始的时候猪站在(1,1),他的目标是走到(n,m)。他只会往(r+1,c)或(r,c+1)走。猪经过的路径要构成一个回文。数一数从(1,1)到(n,m)有多少条路径。答案可能非常巨大，请输出对 109+7 取余后的结果。

思路：一看就知道是一道双线程的dp，就跟以前做的更难的矩阵取数问题一样。

所以当然也是开三维啦，dp(i)(j)(k)：走i步到(j,2+i-j)(k,n+m-i-k)的漂亮路径数。

边界条件是分奇偶的，就是搞个st来表示最长的步数，然后分奇偶来赋值1，这里也要注意偶数步数的时候，两个当前的位置应该是相邻的，要判一下。

转移也是很简单的，倒推就可以了。dp(i)(j)(k)=dp(i+1)(j)(k)+dp(i+1)(j-1)(k)+dp(i+1)(j)(k+1)+dp(i)(j-1)(k+1)。

因为三维而且用long long数组会很大所以当然是用滚动数组啦。

因为是滚动数组所以每次dp(i%2)(j)(k)要清零呀QAQ因为这个WA了一发QAQ

细节有点多越界啊啥的要注意呀qwq

听说这是CF DIV2的E题难度？那我做出了真是美滋滋hhh

3.31

51nod1043

题意：1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。

思路：今天做一个数位dp。

因为这个数字由两部分组成，所以考虑dp(i)(j):长度为i和为j的数字，则dp(i)(j)=∑dp(i)(j-k),0<=k<=9。

这里还要考虑是否有前导0，前半部分是不能有前导0的，后半部分是可以有的，可以分别统计dp1,dp2，区别就在于边界条件，如果可以有前导0的话dp1(1)(0)=1。

统计的时候用乘法原理。

4.1

CodeForces919D

题意：给出一张有向图，给每个结点一个字母，定义路径的值为这条路上的出现最多的字母出现的次数，求这张图中所有路径中路径的值的最大值，如果可以任意大的话，就输出-1。

思路：容易可以看出这是一个树形dp，因为每个结点都只是一个小写字母，所以dp(i)(j)：到i点j出现的最大次数，有转移方程dp(i)(j)=max(dp(k)(j)),k为i的子结点，而且当j==a[i]-‘a’时，有dp(i)(j)++，边界条件是叶子结点的dp(i)(a[i]-‘a’)为1。

考虑到任意大的情况就是有环，所以可以在dfs求dp的同时判环。

这里我智障了QAQ数组开小了导致一直WA…又查不出错 以后就

#define MAXN 300010

这样写吧。

也可以用拓扑排序的写法，这里状态转移指的就是父节点而不是子节点了。

因为拓扑排序的步骤：

(1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;

(2)从有向图中删去此顶点以及所有以它为尾的弧;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

如何通过拓扑排序判断图中是否有环：拓扑排序之后，若还剩有点，则表示有环。

4.6

计蒜客题

题意：有一个长度为n且由a和b组成的字符串，他把这个字符串划分成了若干段回文子串，如”abbaaba” => “abba” + “aba”是一种划分方案。每个划分方案对答案的贡献是，划分的不同部分的长度的乘积，上述贡献即为4*3=12。问所有有效划分方案贡献的总和是多少。对答案mod1000000007输出。

思路：回文的动态规划好像经常用的是一维的，而且转移方程也类似。

dp[i]:前i个字符的最大贡献。

以题目为例子，dp[0]=1，dp[1]=1，dp[2]=dp[1]×1，dp[3]=dp[2]×1+dp[1]×2，dp[4]=dp[3]×1+dp[0]×4（这里解释了为什么dp[0]=1），dp[5]=dp[4]×1+dp[3]×2。

所以有转移方程dp[i]=dp[j-1]×(i-j+1)(i到j为回文)。

预处理一下i到j是否为回文（见上文）。

4.11

ZOJ4019

最近一直在做其他题…所以之前的题到现在才补emmmm

题意：给出两类物品，这两类物品的单位价值分别是k1，k2，再给出这两类物品中每个物品所占的体积，现有体积为c的背包，定义价值为单位价值*当前背包剩余体积，问背包能装下的最大的价值。

思路：我刚开始想的是把两类物品直接dp，像这样dp(i)(j):选到第i个物品背包剩余体积为j，但是这样是不可行的，因为c<1e7，所以考虑其他思路，看到只有两类，而且这两类价值都是一样的，所以这肯定是要利用的一个条件。

先贪心，因为每类物品价值是一样的，所以尽可能放体积小的，排序一下。

考虑dp(i)(j)：取前i个第一类，前j个第二类的最大价值。

所以有转移方程：dp(i)(j)=max(dp(i-1)(j)+k1×(c-prea[i]-preb[j]),dp(i)(j-1)+k2×(c-prea[i]-preb[j]))（prea,preb都是前缀和）。

边界条件就是dp(0)(i)和dp(i)(0)。

因为T有500组，500×2000×2000=2e9，所以肯定要剪枝。

由单调性容易想到如果一次c-prea[i]-preb[j]小于0，后面肯定都不用算了，这里我还犯了个小错误，我是直接退出两重循环了，其实并不是啊hhh，单调性是只属于每一重的。

dp也不要每次清零了，直接赋值就好了，所以ans每次算出dp(i)(j)后直接更新。

说一句，不要总是乱交，在submit之前再看看自己的程序，要确定没问题之后再交啊。

4.18

CodeForces940E

题意：给你一个数列，你可以划分成几个部分，每个部分的价值是除去前[len/k]小的数的和。求价值的最小值。

思路：因为总和不变，就是要让被删除的数字的总和尽可能大。

先是猜测分组的len肯定只有k和1，因为k可以保证不会浪费，尽可能使len/k整除，这样的贪心可以删除尽可能多的数字。

贪心之后就可以dp了，dp(i):到第i个数字删掉的元素的最大和。

转移方程：dp(i)=max(dp(i-1),dp(i-k)+min(a[i-k+1],a[i-k+2]…a[i]))，即该数字一个数一组和该数字所在的组(len=k)被删掉最小值的情况。

所以只要用各种方法查询最小值就可以了，我用的是ST表。

CodeForces932E

题意：给定n,k,求

$$\sum_{i=1}^nC_n^i*i^k$$

,其中n<=1e9,k<=5e3。

思路：没有思路的一道题…刚开始以为这是有公式的或者可以找规律的…等打出表发现自己太天真了…看了题解 有三种解决方法 一种是求导+dp 还有一种是组合数学+dp 还有一种斯科林数的方法 都好强啊orz。

看了一种自己能够接受的，组合+dp的思路。

其实这个式子可以转化成一个组合问题：把n种物品放入k个箱子（每个箱子只能放一种）的方案数。妙啊orz。

那么如何解决这个问题呢？

这里就要用dp了，dp(i)(j):到第i个箱子放j种的方案数。看起来n<=1e9不能这样设计状态，实际上这是假的，箱子总共也就k个呀…

转移方程就可以写了：dp(i)(j)=dp(i-1)(j)×j+dp(i-1)(j-1)×(n-j+1)，即第i个箱子选哪一种的情况。

那么答案如何表示？

答案就是$\sum_{i=1}^n dp[k][i]*2^{n-i}$，为什么这里要乘$2^{n-i}$呢？因为考虑到问题里可能存在比如说预选了4种，但是实际上可能只用了2种的情况，所以这里也要存在这种情况，所以剩下的n-i种可能被选了可能没被选。

好厉害啊这道题居然还可以这么转化orz学到了hhh

4.26

CodeForces946F

题意：定义F(x)为F(x-1)与F(x-2)的连接（其中F(0) = ‘0’,F(1) = ‘1’）。
给出一个长度不超过100的字符串s，询问s在F(x)的所有子序列中出现了多少次。

思路：

没思路看题解做的QAQ

dp(i)(j)(k):s(j,k)在F(i)的所有子序列中出现的总次数。

一般情况，

dp(i)(j)(k)+=dp(i-1)(j)(k)，

dp(i)(j)(k)+=dp(i-2)(j)(k)，

dp(i)(j)(k)+=dp(i-1)(j)(l)*dp(i-2)(l)(k)，

在dp(i-1)(j)(k)中当k==n的时候，f(i-2)中可以随便选，

在dp(i-2)(j)(k)中当j==1的时候，f(i-1)中可以随便选，

所以，

dp(i)(j)(k)+=dp(i-1)(j)(k)*(k==n?(2^len(f(i-2))):1)，

dp(i)(j)(k)+=dp(i-2)(j)(k)*(j==1?(2^len(f(i-1))):1)，

dp(i)(j)(k)+=dp(i-1)(j)(l)*dp(i-2)(l)(k)。

7.5

luoguP1140

题意：给出两个基因序列，根据求出基因相似度。不等长可以在其中加-，如。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

思路：

$dp[i][j]$ :前i个与前j个匹配的最大基因相似度。

$dp[i][j]=max\{dp[i][j],dp[i-1][j]+val(a[i],'-'\}$：a[i]与’-‘匹配。

$dp[i][j]=max\{dp[i][j],dp[i][j-1]+val('-','b[j]'\}$：’-‘与b[j]匹配。

$dp[i][j]=max\{dp[i][j],dp[i-1][j]+val(a[i-1],b[j-1]\}$：a[i]与b[j]匹配。

注意边界条件即可。

7.13

GCPC2015J

题意：有个地方只能用金币和银币，它们的汇率为g，刚开始你有c个金币，他要去n个商家那里买东西。每个商家找零只能用一整袋的银币，每袋银币的个数为pi，商家分为greed，honest和generous三种类型，greed找零的时候是向下取整的，honest是四舍五入的，generous是向上取整的，每个商品的价格为si(si<g)，而且你很同情generous，你有银币可以直接付的话就直接付。问你最多可以买几个商品。

思路：

$dp[i][j][k]$:处理完第i个商品还剩j个金币k个银币时能买到的最多商品。

有转移：

不买：$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])$；

用银币买：$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k+s_i]+1)(k+s_i≤g*c)$；

用金币买:$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j+1][k+找零]+1)$，

其中找零可以借助ceil,floor,round（四舍五入）函数计算，

因为对于generous如果银币可以付的话就不用金币付，所以当k+找零>=si的话，就不能用金币买了。

这里注意初始化dp数组要为-INF而不是0，因为有些状态是不能到达的。

边界条件是$dp[0][c][0]=0$。

8.21

CTU2017F

题意：给出n个数字，一对相同的数字里面可以包一对相同的数字，同理可以一直包下去，问这样的数字对数最多有多少。

思路：

$dp[i][j]$：i到j这样的数字的最大对数。

有转移：

$dp[i][j]=max(dp[i+1][j],dp[i][j-1])$;

如果$a[i]==a[j]$，有转移$dp[i][j]=max(dp[i][j],dp[i+1][j-1]+1)$。

8.27

做几道区间DP，区间DP常常是外层循环是长度，内存循环是起点。

POJ2955

题意：给出一个含’(‘，’)’，’[‘，’]’的括号序列，求最长的括号匹配子序列。

思路：区间dp的典型套路，$dp[i][j]$：[i,j]区间最长的括号匹配子序列。除了跟上题一样的转移外，还有$dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j])$，就是()()这种情况。

POJ1651

题意：给出n个数字，每次取出一个数字a[i]，价值为$a[i-1]*a[i]*a[i+1]$，直到只剩下最前面一个数字和最后面一个数字。问最小价值为多少。

思路：$dp[i][j]$：[i,j]最小价值。

$dp[i][j]=max(dp[i][k]+dp[k][j]+a[i]*a[k]*a[j])\ |\ i+1\le k \le j-1$。

从长度为3开始循环，外层是长度，内层是i，再枚举k。

如何理解？

如果有三个数字，$dp[1][3]=dp[1][2]+dp[2][3]+a[1]*a[2]*a[3]$。

如果有四个数字，$dp[1][4]=max(dp[1][2]+dp[2][4]+a[1]*a[2]*a[4],dp[1][3]+dp[3][4]+a[1]*a[3]*a[4])$。

如果有五个数字，

$dp[1][5]=max(dp[1][2]+dp[2][5]+a[1]*a[2]*a[5],dp[1][3]+dp[3][5]+a[1]*a[3]*a[5],dp[1][4]+dp[4][5]+a[1]*a[4]*a[5])$。

画一画会明白。

因为对于一个区间来说，最后肯定只剩下最前面的数字和最后面的数字，所以对于$dp[i][k]$和$dp[k][j]$这两个区间剩下的数字肯定只有a[i],a[k],a[j]，所以转移是这样子的。

LightOj1422

题意：一个人要按顺序穿着n件衣服，身上的衣服可以穿好几件，但是如果脱掉以后这件衣服就报废了。问最少要几件衣服。

思路：$dp[i][j]$：从i到j天最少要穿的衣服。

对于第i件衣服，如果之后的区间不再重复利用了，这种情况的转移为$dp[i][j]=dp[i+1][j]+1$。

如果这件衣服在后面的区间可以重复利用，则选择区间的穿的衣服种类相同的天数，$dp[i][j]=dp[i][k-1]+dp[k+1][j]$，因为要选第k天作为重复利用，那么要把[i,k-1]的衣服一件一件脱下来，那么[i,k-1]和[k+1,j]的代价是要独立算的。

9.25

徐州网络赛B

题意：有n轮游戏，有初始分数m，有A和B两个人，每轮游戏可以有三个选项，加某个数，减某个数，取相反数。A总是想得到GE，B总是想得到BE，GE即最后分数>=k，BE即最后分数<=l，其他都是NE。如果自己不能赢的话，那宁愿NE也不要对手赢。A先手。问最后的结果。其中$1≤n≤1000, −100≤m≤100$。

思路：可以想到可以用记忆化搜索。状态就是到第i轮分数为j的结果。1000*200是可以接受的。对于A来说，尽可能要GE，不行的话就NE，之后才是BE，对于B来说，尽可能要BE，不行的话就NE，之后才是GE。脑补一下写个记忆化搜索就可以了。