【Just AC it】IA 动态规划 小结
综述：
8#21开的题目，开学8#26-9#1休息了一个星期，然后今天把最后3题写了。
题目质量很高。
能不看题解做出来的就3道：A（树状数组模拟）、C（做过）、E（不算难的树形DP）；其他5道都多少要看了题解才行。A题想不出递推方程，B题卡在转化为LIS那里，D题知道是状压但是思路有点小问题，F卡在优化状态+化简方程，G根本没什么思路。
DP最初的本意是区别与静态规划来解最优化问题，现在DP的概念广义上已经和数学中的递推、分治一样。
这里的选题也是用的广义的概念，除了B、D、E、F是最优化问题，A是数学递推，C是博弈，G是可行性问题。
A - And Then There Was One
数列递推
约瑟夫问题求最后一个，n = 1e4。
链表模拟O(n^2)，递推O(n)。不过关系式比较难想。假设n = i，起点为0，那么去掉第一个后就变成了n = i-1，起点为k了；那么答案就是f(n-1)+k了。
其实模拟也能过的，只不过不是用链表，而是用树状数组。每次删除都相当于求目前元素后面的第k大数。ZH写过了，代码也不算长。O(nlogn)
B - Prince and Princess
LCS变形
初次看题目以为就是LCS（最长公共自序列），LCS的最低复杂度是O(n^2)。
不知如何优化，然后看题解了。
这里的LCS有个特殊的地方，每个字符只可能出现一次。利用这点可以优化。
假如用A序列作为参照次序，把B中的字符全转化为在A中的次序，就转化为求LIS（最长不下降自序列），O(nlogn)。
C - Game of Sum
DP解博弈问题
比较值得研究的内容，这类做的比较少，现在还没什么心得，以后研究博弈专题的时候在来了。
E - Placing Lampposts
树形DP
做过一些树形DP、分治的题了，但这道题目还是给了一些启示。
开始我想的做法是维护两个指标，看了LRJ的讲解，用x = v1*M + v2来代替两个指标。太神奇了。跟求网络流的边树把边权值改为w*M+1有异曲同工之妙。可惜我没想到过。
分治方程比较简单，我的方程跟LRJ有点不同：
f[i][1] = sum{ min{ f[j][0] +1 , f[j][1] } } + M;
f[i][0] = sum{ f[j][1] + 1 } ;
int vd[LN],f[LN][2];
void DFS(int fv)
{
vd[fv] = 1;
int size
= elist[fv].size();
for (int i
= 0;i
< size;i++)
{
int ev
= elist[fv][i];
if (vd[ev])
continue;
DFS(ev);
f[fv][1] += min(f[ev][0]+1,f[ev][1]);
f[fv][0] += f[ev][1]+1;
}
f[fv][1] += M;
}
void DFS(int fv)
{
vd[fv] = 1;
int size
= elist[fv].size();
for (int i
= 0;i
< size;i++)
{
int ev
= elist[fv][i];
if (vd[ev])
continue;
DFS(ev);
f[fv][1] += min(f[ev][0]+1,f[ev][1]);
f[fv][0] += f[ev][1]+1;
}
f[fv][1] += M;
}
我觉得这种写法更好理解些。
F - Robotruck
动态规划时间优化，经典。
可以抽象为一个分段问题。 将一个数列切分为M段，每段的重量<= C ，有一个计算花费的公式，求最少花费。
抽象后，容易得到朴素的方程： d[i] = min{ d[j] + dis2origin[j+1] + dis(j+1,i) + dis2origin[i] }
时间O(n^2)，需要优化时间，怎么优化呢？只能去试试减少寻找j的时间。
应用区间和=前缀差： d[i] = min{ d[j] + dis2origin[j+1] + sumd[i] - sumd[j+1] + dis2origin[i] }
分离： d[i] = min{d[j] + dis2origin[j+1] - sumd[j+1]} + sumd[i] + dis2origin[i]
注意到现在min{..}里面的只跟j有关，与i无关，就成了一个区间最值的问题。如果使用单调队列的话，总时间O(n)。
D - Hackers' Crackdown
状压DP
初看题目好像是一个图论问题，但去除无关因素，抽象一下是个类似背包的问题。
做过比较多的状压，这个状压的转移是：从子集推过来。
学习了枚举子集的写法： for (int S0 = S;S0;S0 = (S0-1) & S) ；很巧妙的写法
G - Sharing Chocolate
状压DP
这道题目真心思路很难想到。求可行性的问题，没有常见的模型可以套用，也比较难想到能用DP解决。
不过线索还是有的，初看n = 15，可以想到状压表示集合。
如何转移？大的矩形可以由两个小的矩形推过来。
然后优化下状态数。
迷惑：怎么计算这道题的时间复杂度？假如书上的时间复杂度是对的，那么记忆化搜索比递推的优势大这么多？很少见递推不能过记忆化能过的题。
这道题把 for (int S0 = S;S0;S0 = (S0-1) & S) 敲成了 for (int S0 = S;S0;S0 = (S0-1) &
S0) ，60行代码，找了1个半小时有木有。
S0) ，60行代码，找了1个半小时有木有。