@动规个人总结二-DP-动态规划
i207M
·
·
个人记录
给出一棵树的欧拉序，问有多少种可能
每个节点有编号，但不唯一；N<=300
考虑到欧拉序上一段区间表示一棵子树，且前提是l,r的编号相同，可以区间DP；
我们枚举第一棵子树的位置：
f[l][r]=f[l][r]+dp(l+1,k-1)*dp(k,r)(s[l]==s[r])
边界条件是f[i][i]=1,f[l][r]=0(s[l]\neq s[r])
注意两个子区间的端点：l+1,r
无根树最大流
二次扫描和换根法
环形DP
1.枚举第一个点是否和第N个点连接，做两次DP；
2.断环成两倍长的链；
数学期望DP往往倒序进行
Never·island
思想：将一整个区间根据关键点的位置，拆成很多段，对于每段、关键点单独考虑，往往可以将复杂、纠缠的问题简单化
写挂了，还是看看题解吧
在推导式子的时候，可以将出现很多次的部分设为一个变量，这样可能更能发现其中的规律
一些问题难以找到子结构，考虑：不要采取确定的绝对表达，而是按照相对顺序定义，这样会使问题产生子结构
当DP不知如何优化，尝试交换维度
吃夜宵
给定N个物品有价格，手上有M元钱，求买物品直到剩下的前买不了任何物品的方案数；0<=M<=1000，0<=M<=1000；
首先，如果可以的话，全部买是一种方案，先统计上，防止漏；
然后，我们对物品按价格从大到小排序，依次DP；每次，我们枚举当前物品就是不选择的最小物品，这样，所有小于它的物品都必须选，大于它的物品选不选都可以，于是就统计答案；
sort(w + 1, w + 1 + n, greater<int>());
for (ri i = n; i >= 1; --i) {
dsum[i] = dsum[i + 1] + w[i];
}
f[0][0] = 1;
if (dsum[1] <= m) ++ans;
for (ri i = 1; i <= n; ++i) {
for (ri j = m - dsum[i + 1]; j >= 0 && j > (m - dsum[i + 1] - w[i]) ; --j) {
(ans += f[i - 1][j]) %= md;
}
for (ri j = m; j >= 0; --j) {
f[i][j] = f[i - 1][j];
if (j >= w[i]) (f[i][j] += f[i - 1][j - w[i]]) %= md;
}
}
背包问题
输出字典序最小的最优方案
输出方案很简单，但如何保证字典序？由于我们的每一步DP只能保证最后一个选择的是什么，我们无法记录之前的所有状态；
所以我们倒序枚举，这样我们当前枚举的一定是字典序最小的，我们要尽量选它，也就是当f[i][v]==f[i-1][v]并且f[i][v]==f[i-1][v-c[i]]+w[i]的时候我们要选择后面这个方案.因为这样选择的话,我们会得到更小的字典序；
求前k优解
我认为这是DP求第k优解的通用方法；
初始时$f[0][0][1]=0$，其他均为负无穷；
然后，k优解一定是由之前的解转移过来，p1表示下一个轮到$f[i][j][p1]$，p2表示下一个轮到$f[i][j-v[i]][p2]$，然后选择最大的更新；
```
memset(f,0xcf,sizeof f);
f[0][1]=0;
for(ri i=1;i<=n;++i)
{
for(ri j=vol;j>=v[i];--j)
{
int p1=1,p2=1,cnt=1;
while(cnt<=k)
{
if(f[j][p1]>f[j-v[i]][p2]+w[i])
cur[cnt++]=f[j][p1++];
else cur[cnt++]=f[j-v[i]][p2++]+w[i];
}
for(ri h=1;h<=k;++h) f[j][h]=cur[h];
}
}
```
## 转移时注意更新顺序！！！
## BZOJ 2064
题意：给定一个初始集合和目标集合，有两种操作：1.合并集合中的两个元素，新元素为两个元素之和 2.分裂集合中的一个元素，得到的两个新元素之和等于原先的元素。要求用最小步数使初始集合变为目标集合，求最小步数。
科学的做法需要我们仔细观察性质…
用一个形象的方法来讲:
假设我们一开始在数轴零点上,每过来一个原始集合的数字x我们就向右走x,过来一个目标集合的数字y我们就向左走y.
每一对匹配的原始和目标集合的子集都可以让我们走一圈回到原点.
反过来,在数轴上走一圈回到原点意味着我们找到了一对匹配的子集.
那么用f[S1][S2]表示已经用了原始集合S1的数字和目标集合S2的数字,最多能够多少次经过原点.预处理每个子集的和.
然后就$O(n2^n)$了
## 见到$Max<=2^{30}$，是非常适合折半拆位做的
[HNOI2007]梦幻岛宝珠，拆位；为了平衡复杂度，以$b<=12$为界，分别做DP；
当然正解是二进制DP；
## UVA10559 Blocks
有n个带有颜色的方块，没消除一段长度为x的连续的相同颜色的方块可以得到x^2的分数，让你用一种最优的顺序消除所有方块使得得分最多。n<=100
首先想到是区间DP；但是又遇见了区间DP经典的难点：一个点的贡献无法统计，产生贡献的可能在区间之外；
于是又遇上了经典讨论：约定；$f[l][r][k]$表示$[l,r]$区间，并且右边还有k个和r颜色相同的盒子，的最大得分；转移的时候有两种：
1.消掉右侧的盒子；$f[l][r-1]+(k+1)^2
2.消掉中间的盒子，和右边拼起来：f[l][i][k+1]+f[i+1][r-1][0]；
注意，在第二步，找分割点时，并不是只有一种可能，事实上，区间内的每一个同色点都有可能成为同色点，都要枚举；
AT2567 RGB Sequence
感觉我的弱项是暴力的DP状态设计，往往想不到；
## Split the sequence
记录一个核心知识：
给出一个长度为 N 的非负整数序列, 要重复下面的操作 K 次：选择一个序列, 然后把它分成两个新的非空序列.每次操作后将获得那两个新序列和的乘积的得分. 求最大总得分.
如何求“分K次，得分为和的乘积”？
**两组数和的乘积=两组数两两相乘的和**，分K次等于分成$k+1$段，于是$f[i][j]$就有了，斜率优化；
## 序列DP一个trick：枚举最大的数字在哪
## dp压位
dp状态存不下时，考虑合并维度；例如$f[i][len][s]$表示从i出发走len步，能否走出s状态；存不下？我们强制在每个s的最高位补一个1，这样我们仅用2s的空间就存下了；