P1437 敲砖块
如果我们选择了一个点那么以它为顶点的直角指向左上角的等腰直角三角形中的所有点都应该被选定。
那也就是说最后的图形是若干的直角三角形框住的元素的权值和。
我们考虑一列一列考虑最后的图形，发现前一列的长度小于等于当前列的长度加一，观察发现这是充要的，用这个性质 dp 即可。
设 \(f_{i,j,k}\) 表示考虑到第 \(j\) 列，选择了前 \(i\) 行，共选择了 \(k\) 个格子的最大价值，转移显然。
\[f_{i,j,k}=\max_{t=0}^{i+1}\{f_{t,j-1,k-i}+\sum_{t=1}^{i}a_{t,j}\} \]直接前缀和做是 \(O(n^5)\) 的，常数很小，可以通过，但是很容易通过前缀 max 优化到 \(O(n^4)\)。
P2549 计算机写作文
比较简单的一道题。
很容易想到把字符串反转过来就成了从前往后填，先随便写一个 comp 函数比较两个字符串，显然要按照某种策略排序后 dp。
排序策略为：若 \(s\) 排在 \(t\) 前当且仅当 \(s+t>t+s\)，证明如下。
我们设 \(r\) 表示当前的最佳答案，在枚举完 \(s,t\) 后的答案为 \(r'\)，有三种情况。
-
\(r=r'\)，\(s,t\) 都没有对答案产生贡献，那么 \(s,t\) 顺序任意。
-
\(r'=r+s\) 或 \(r'=r+t\) 仅有一个对答案产生了贡献，顺序也可以任意。
-
\(s,t\) 都对 \(r\) 产生了贡献，而又因为 \(s+t>t+s\) 所以先 \(s\) 后 \(t\) 是更优的。
所以但 \(s+t>t+s\) 时 \(s\) 排在 \(t\) 前是一定不劣的。
最后就是一个背包了设 \(f_i\) 表示长度为 \(i\) 的字符串的最佳答案。
正常背包做即可，最后的答案为 \(f_D\)，注意一下前导零的问题。
CF254C Anagram
因为可以随意变换所以合法的条件就是
\[\forall i\in \Sigma, cntS_i=cntT_i \]\(\Sigma\) 是字符集，\(cntS_i\) 表示 \(S\) 字符串中 \(i\) 的个数。
我们记 \(c_i=cntS_i-cntT_i\)。
然后从前往后遍历所有 \(c_i>0\) 的下标看看能不能填比它小并且 \(c_i<0\) 的字符，如果能找到比它小的，那么就填最小的合法字符，否则看这个字符是否一定要换，具体就是看在它后面的 \(i\) 的个数是否能够保证能够成功替换。
CF1176F Destroy it!
如果没有 10 次一暴击的条件我们直接对每轮做一次 01 背包，每轮取最大的计入答案即可，但是有这个限制我们就可以把攻击次数对 10 取模后的结果计入 dp 值。
设 \(f_{i,j}\) 表示进行了 \(i\) 轮后攻击次数对 10 取模结果为 \(j\) 的最大伤害，对于每一轮我们记 \(g_{i,j,0/1}\) 表示选了 \(i\) 次攻击，花费为 \(j\) 是否翻倍过的最大伤害。
转移方程式为：
\[\begin{matrix} g_{i,j,0}=\max\{g_{i-1,j-c_t,0}+d_t\} \\ g_{i,j,1}= \max (\max\{g_{i-1,j-c_t,0}+2d_t\},\max\{g_{i-1,j-c_t,1}+d_t\}) \end{matrix} \]\(f_{i,j}\) 转移的时候枚举当前轮选取 \(p\) 次攻击，若 \(j+p \ge 10\) 那么就可以进行翻倍攻击，代码非常好写。
标签：10,杂题,cntS,答案,max,字符串,合集,dp From： https://www.cnblogs.com/igac/p/18335483