好虚啊。。。

线段树勉强写完了单点更新的一组题。。。。16道题写了20天。。。

后面的带lazy标记的简直难度上天啊orz...刷不动==

然后想回头复习下数位dp吧。。。发现也是各种被卡。。。

题目链接

题意：给出l,r,k，定义f(n,k)为将数n分成左右两个非空的部分，再求和之后能被k整除的方案数。

现在问区间[l,r]中所有f(i,k)的和。

题目链接

题意：统计区间[a,b]里数字1出现的次数。

思路：数位dp。

收获是，dfs传递的参数可能是为了判断符合条件的答案（比如不要62中的preis6等）

题目链接

题意：给出一串只由数字'4'和'7'组成的串。两种操作，一种是询问整个串中最长非下降子序列的长度，另一种给出区间[l,r]，将区间中的没个数反转，反转的定义为，4变成7,7变成4.

题目链接

题意：一个循环数列，两种操作，一种是把某段区间中加上v，另一种是询问某区间的最小值。对于每个询问，输出答案。

思路：区间更新+区间询问的模板题....

我学不会dp不是因为我智商低，而是因为没有足够好的资料。 ** 我学不会dp不是因为我智商低，而是因为没有足够好的资料。** ** 我学不会dp不是因为我智商低，而是因为没有足够好的资料。**

题目链接

题意： 给定两个序列，求它们的最长公共递增子序列的长度, 并且这个子序列的值是连续的 思路：以值为连续做入手点。

很显然个鬼咯 dp[a[i]]表示以a[i]结尾的最大长度。 dp[a[i]] = dp[a[i-1]] + 1 对于b序列一样。

题目链接 题意：已知 f(1, j) = a[j] f[i][j] = min (f[i-1][j],f[i-1][j-1]) 然后给出 n n≤1E5​​ 个数（a[i] a​i​​≤1E4​​)，给出 m组查询（m<=1E5），每组两个数 x,y 问 f(x,y) 是多少。

题目链接

题意：n个数，分成若干段，每段的代价为 ，求最小代价。

思路：dp。

状态方程很显然个鬼。。。

dp[i] 表示处理完前面i个数的最小代价。

dp[0] = 0 ;

dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。

浅谈数形结合思想在信息学竞赛中的应用

参考博客

这个东西英文好像叫做：convex hull trick

Convex_hull_trick_wiki codeforces convex hull trick

简单说说我的理解：斜率优化是一种数形结合的思想。。。

对于一个dp的若干状态。。。有些状态是不会对答案有贡献的。。。这些我们就可以不考虑。。。