link
注意到\(1\leq a_i\leq 9,1\leq j\leq a_i\)
设\(f(i)\)表示到达位置\(i\)需要的最小代价。
题目中的两种转移可以分别处理。
\(1.\)枚举步长\(j\)即可。\(f(i)=f(i-j)+\frac{j}{a_{i-j}}\)
\(2.\)维护\(lst(a_i)\)表示上一个与\(a_i\)相同的\(a\)的位置\(j~f(i)=f(j)+1\)
需要注意的是分数运算不能再每次转移中\(logV\)处理，总时间复杂度为\(O(9nlogV)\)
我们考虑优化分数处理的过程，容易想到需要将分母去掉。
对于\(\frac{j}{a_{i-j}},a\in\lbrace 1\dots 9\rbrace\)，在分子乘上\(2520\)即可消去分母\(a_{i-j}\)。
\(2520=lcm(1\dots 9)\)
\(1.f(i)=f(i-j)+\frac{j\times2520}{a_{i-j}}\)
\(2.f(i)=f(lst(a_i))+2520\)
\(Ans=\frac{f(n)}{2520}\)
link
设\(f(i)\)表示到达位置\(i\)需要的最小次数。
\(f(i)=min_{j<i\leq nxt(j)}^j\lbrace f(j)+1\rbrace\)
时间复杂度\(O(n^2)\)
我们尝试转化方程形式。
\(\forall j,f(j)=min\lbrace f(i)+1\rbrace~ [i<j\leq nxt(i)]\)
由刷表法的转移方程，我们可知\(\forall j,f(j)\geq f(i)~ [j>i]\)
\(\forall j,f(j)+1\geq f(i)+1~ [j>i]\)
所以对于\(i<k\leq nxt(i)\vee j<k\leq nxt(j)\vee j>i\)，\(f(i)\)不劣于\(f(j)\)。
维护一个\(lst\)表示目前转移到的\(f\)下标的最大值。
\(\forall j,f(j)=min\lbrace f(i)+1\rbrace~ [lst<j\leq nxt(i)]\)
每个\(f\)只被转移一次，时间复杂度\(O(n)\)。
link
显然状压每个人的管辖区\([E_i,E_i+5)\)
设\(f(i,S)\)表示考虑前\(i\)个人，\([i,i+5)\)的状态为\(S\)的答案。
\(f(i,S)=max\lbrace f(i-1,S[i,i+4)),f(i-1,S[i,i+4)|1)\rbrace+S的贡献\)
我们需要预处理\(S\)的贡献。
设\(g(i,S)\)表示状态\([i,i+5)\)的贡献，输入时顺便处理即可。
需要注意的是，状态是对于\(i\)的相对位置，需要把环上的位置转化为对于\(i\)的相对位置。
\(相对位置=(环上位置-i+n)\)%\(n\)
\(f(i,S)=max\lbrace f(i-1,S[i,i+4)),f(i-1,S[i,i+4)|1)\rbrace+g(i,S)\)
注意，\(f(1,)\)由\(f(0,)\)转移过来，而环上的\(0=n\)，为了统计答案，我们需要\([n,n+5)\)的确定状态。
当我们枚举的\([n,n+5)\)的状态时，代表着\([0,0+5)\)的状态也被确定了。
所以只有从枚举的状态\(f(0,[n,n+5))\)转移才是合法的。
link
简化题意：去掉一些边，使得图上，没有偶环，求最小代价。
反向考虑，给定一棵树和一些非树边，加入一些边到树上，使得图上没有偶环，求最大边权和。
首先，如果边\((u,v)\)会使得\(u\rightarrow v\rightarrow LCA(u,v)\rightarrow u\)形成一个偶环，则\((u,v)\)不能选择。
其次，如果两条边分别的奇环在树上有共同边时，那么去掉共同边，也会产生偶环（\(2|x+y-2k\)）。
所以需要在树上选择一些不相交的非树边使得权值和最大。
考虑\(30pts\)的链：
在一条链上选取若干不相交非树边其实就是一个线性dp，是简单的。
设\(f(i)\)表示考虑了前\(i\)个节点，第\(i\)个节点被覆盖的答案。
\(f(i)+w(u,v)\rightarrow f(v)[i\leq u]\)
时间复杂度\(O(nm)\)
考虑把链的思想延续到全局，注意到出度\(\leq 10\)，所以考虑状压，把每个子树看作一条链处理。
对于每条非树边\((u,v)\)在\(LCA(u,v)\)处考虑，设\(f(u,S)\)表示以\(u\)为根的子树中，\(S\)中儿子未考虑的方案数。
转移分类讨论：
\(1.\)不选\((u,v)\)
\(f(lca,S)=\sum_{x\in son\wedge x\notin S}f(x,\emptyset)\)
\(2.\)选择\((u,v)\)
对于\((u,v)\)，它能带来的价值是\(value(u,v)=w(u,v)+\sum_{x\in u\rightarrow v}^{fa(x)\neq lca\wedge x\neq lca}f(fa(x),\lbrace x\rbrace)\)
若\(x\rightarrow lca\rightarrow y\in u\rightarrow v\wedge x,y\in son_{lca}\)
\(\forall S,x,y\notin S\)
\(f(lca,S)\leftarrow value(u,v)+f(u,S\cup\lbrace x,y\rbrace)\)
\(Ans=\sum w(u,v)-f(1,\emptyset)\)
时间复杂度\(O(mlogn+n2^10)\)
其实就是仙人掌