抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 常见数位dp如果一个在数字上的计数问题只与数位和数的大小有关的时候 我们可以尝试用数位dp来解决。最经典的就像不要62那道题。 数位dp状态我们常常设dp[val][len][limit][lead...

理论篇

决策单调性

对于一类一维$dp$,若有转移$dp[i]=min/max(dp[j]+w(i,j)) 0<j<i$,并假定$pri[i]$为到$dp[i]$的最优转移$j$,如果$pri[i]$关于$i$单调,那么我们称该$dp$具有决策单调性。

对于一类二维$dp$,如果有转移$dp[i][j]=min/max(dp[i][k]+dp[k+1][j]+w(i,j)) i<=k<j $并假定$pro[i][j]$为到$dp[i][j]$的最优转移$k$,如果$pri[i][j]$关于$i$单调,且关于$j$单调,那么我们称该$dp$具有决策单调性。

四边形不等式

对于二元数论函数,$w(i,j)$,若满足$a\le b\le c\le d$恒有 $w(a,d)+w(b,c) \ge w(a,c)+w(b,d)$则该二元函数满足四边形不等式

他的充要条件是: 若$a\lt b$ 恒有$w(a,b)+w(a+1,b+1) \ge w(a,b+1)+w(a+1,b)$

可以理解为,交叉小于包含

区间包含单调性

对于二元数论函数,$i<j$的$w(i,j)$ 我们将参数看做区间,定义区间的包含为偏序关系, 若$w$的值关于该偏序关系单调,则称该函数具有区间包含单调性。

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 给你一棵n个节点的树,要你求出包含每个点的连通点集的数量。答案对1e9+7取模。 两次dfs,第一次处理每个节点的子孙方向的联通点集数量,$$dp[i]=\prod _{all.....

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354...