无穷大？ 
Codeforces DP1400 题 大赏
CF628B New Skateboard
大意
给定一个字符串，求其中能被4整除的字串数量。
思路
能被4整除的数字，其末两位数一定能被4整除。所以我们只需枚举末两位能被4整除的所有情况。对于每一个这样的两位数，其前面的所有组合都可以被4整除。而这两位数又分为两种情况：一种是个位数能被4整除。显然，这种情况意味着只能是这单个数字能被4整除，因为我们并不能保证前面的一位数字组合上这个数字能被4整除。另一种是两位数能被4整除，此时同样是任意的前面的数字与之组合能被4整除。下面给出这两种情况的解决方案：
- 如果当前数字本身就能被4整除，那么ans++；
- 如果（当前数字+前一个数字*10）能被4整除，则ans+=i（i为当前数字的下标）。因为对于每一个位置，都有其前面i个的连续组合。
那么只需利用for循环，遍历一遍字符串，就能轻易做出这道题目了。这道题并没有直接用上dp的状态转移方程，但确实有亿点点dp的推理思想。
AC代码
``` #includeCF189A Cut Ribbon
大意：
给一长度为n的缎带，要求将其剪成若干长度为a,b,c的缎带，且缎带数量尽可能多。求这个最大值。注意，这里的缎带必须全部用a,b,c的长度剪且要刚好剪完。
思考
lls尝云：“dp的状态类似于dfs的参数。” 所以，如果直接定义dp的状态有困难，不如先思考用dfs如何解决这个问题。如果要用dfs解决这个问题，我们肯定要遍历选择到了第几个缎带，并枚举剪了几个当前的缎带。这样一来，就类似于完全背包，我们还能用一维数组空间压缩。只需输出dp[m]即可。
AC Code & Comments
``` #includeCF1178B WOW Factor
翻译
给定一个只含“v”和"o"字符串s(长度最大为$10^6$) 求字符串中有多少个wow（一个“w”即为连续的两个“v”）。
分析
对于任意的一个wow，都是由vv...o...vv组成的。所以，当遇到vv时，就令vv的计数器++；当遇到o时，就令vvo的计数器+==vv；当再次遇到vv时，令vvovv的计数器+=vvo（这部操作可以合并到上面的vv，没有冲突）。其思路来源于下面这题：
代码
``` #includeCF691B s-palindrome
这道题和dp似乎没有半毛钱关系。略去。
CF698A Vacations
题目大意
Vasya有n天的假期 每天有四种选择：
0.在这一天，健身房关闭，比赛不进行；
1.在这一天，健身房关闭，比赛进行；
2.在这一天，健身房是开放的，比赛不进行；
3.在这一天，健身房是开放的，比赛是进行的。
在每一天，Vasya可以休息，比赛(如果在这一天进行)，或者做运动(如果健身房在这一天是开放的)。
但Vasya不想连续两天做同样的活动：这意味着，他不会连续两天做运动，也不会在连续两天写比赛。
找出Vasya休息的最少天数
解题过程
由题意不难得出，本题共有三个要素：
- 第几天
- 做什么
- 休息天数
其中，休息天数是所要求的答案。故dp的状态设计正好是两个：dp[i][j]表示第i天做j活动的最多工作（这里我们定义工作，便于理解，当然也可以最少休息天数）天数。j={1,2,3}，表示比赛，健身，与休息。
定义边界
根据我们的定义，当还未开始，即天数为0时，dp[0][j]=0，即没有休息。
状态转移方程
枚举每一天的情况。对于第i天，我们有下列转移方程：
- 当今天是比赛或休息，则明天可以是健身。否则明天健身的状态不存在。
- 当今天是健身或休息，则明天可以是比赛。否则明天比赛的状态不存在。
- 在任何情况下，明天都可以休息。
最终只需输出n-max(dp[n][1],max(dp[n][2],dp[n][3]))，即总天数减去最后一天是比赛、健身、休息中的工作最大值。
AC Code
``` #includeCF1195C Basketball Exercise
题目
给定一个 $2 \times n$ 的矩阵 $\{h\}$，现从中选择若干数，且任意两个数不上下或左右相邻，求这些数的和最大是多少？
思路
状态设计
显而易见，题目中有三个要素：第几列，选或不选选第几行，最大和。这里最大和是最终要求的答案，所以设计一个两维数组，dp[i][j]表示选到第i列、当前列选择的状态时的最大和。我们不妨定义：选第一行为1，第二行为2；不选为0。
边界
根据状态设计，可以看出，当还没选择，即选到第0列时，无论选择的状态为什么，最大和都为0。
状态转移方程
对于每一种不同的情况，我们都要分类讨论：
- 当这列不选，则可以从上一列的选第一行、选第二行或不选中转移，因为如果这列不选，无论如何都不会有相邻的。
- 当这列选第一行，则可以从上一列的选第二行或不选转移来。
- 第二行同理。
AC代码
``` #includeCF1245C Constanze's Machine
题目大意
给定一个字符串，规定可以将字符串中的连续两个nn变成m，也可以把连续两个vv变成w。当然也可以不变。现在请你求出有多少个可能得到的字符串。
解题
这道题可以换个角度思考，不用dp来解。
首先不难看出，我们需要找出几个连续的vv块和nn块，然后把它们的可能数乘起来，就是最终的答案。
那么现在的任务就转化为：给出v...v块和n...n块的长度，算出它的方案数。
我们再来回顾一下所谓方案数的定义（计算规则，这里就统一用字母v来举例了）：对任意的一串字母v...v，将其中每两个v变成一个w，求能有几种最终可能。
下面给出一个例子（5个v）：
vvvvv
首先先考虑只变两个v的情况：
- wvvv
- vwvv
- vvwv
- vvvw
接着是变化四个v：
- wwv
- wvw
- vww
这样一算，共有7种可能。
更一般地，推广到长度为n的“v序列”，我们枚举以下可能：
- 变化两个v：
- wvvv...(n-2个v)
- vwvv...
- vvwv...
- ...w可以一次占有n-1个位置，一共有n-1种。
- 变化四个v：
- wwv...(n-4个v)
- wvw...
- ...一共有n-2种。
- ...
- 变化[n/2]个v（
[]是取整符号，因为要考虑到当n是奇数，最后一个v不够变化两个）：- www...w(v)
- 一共有1种。
所以，显而易见，最终的情况就是(1+2+...+n-1)。
代码时注意
- 根据上面的解析，我们容易知道要使用斐波那契数列。此时请您预处理好fib数列。
- 请注意取模$10^9+7$。应当在fib数列预处理中就要进行。
AC Code
``` #includeCF180C Letter
题意
给你一个字符串，我们每一次操作都可以将一个大写字母变成任意小写字母，当然同理也可以将小写字母变成任意大写字母，问最少操作多少次，能够使得字符串变成前边都是大写字母，后边都是小写字母。
答案
``` #include支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！