poetry

题意：给\(n\)个单词，每个单词有长度和韵脚，然后要把它们组成一个\(m\)行的诗，每行的长度为\(k\)，并且韵尾确定。问可以组成多少种诗。

思路：设\(dp(i)\)表示长度为\(i\)的句子有多少种表示方法。

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

那么转移就是和完全背包一模一样。

当我们转移到\(dp(k)\)的时候就可以记录韵脚为什么的表示种数。

然后对于每一种韵脚弄个快速幂算一下有多少就好了。

由于不同的韵脚是不相关的，所以所有韵脚的答案要乘起来。

sleepy

题意：给一个排列，现在要通过每次移动第一个数来排序，问每次第一个数要向右移动多少位。

思路：首先我们找规律。

如果我们要把一个序列排序，那么肯定最后的那段连续上升子序列是不会动的。

所以我们就是每次把第一个数挪到它应该放到的位置上。

所以每次要挪的距离就是它到那个连续上升子序列的距离加上比它小的个数。

那么用一个\(bit\)存下每个数是否存在，前缀和就是这个数的排名了。

shortcut

题意：给一个图，从每个点有\(c_i\)个奶牛往\(1\)号点走字典序最小的最短路，每条边有一个距离，现在要布置一个『捷径』，长度为\(t\)，从\(1\)号点到任意一个其它的点。问这条捷径会带来多大的便利。

思路：我们首先\(dij\)出最短路，然后算\(prv\)的时候需要注意一下取最小的，那么就可以构出一棵树，即最短路树。

然后我们从每个点沿着\(prv\)往\(1\)跑，跑的途中看我们可不可以在这个地方布置捷径，如果会让我们的距离缩短，那么就可以把这个点的收益加上一个\(c_i\times (dis_u-t)\)。

然后就找收益最大的点就好了。

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄