蒜头君吃糖果 题解
蒜头君吃糖果 题解
到LOFTER上效果更佳 http://www.lofter.com/lpost/30bea8b0_1c66f1e18
我的LOFTER: http://wronganswer.lofter.com/
题面：
emmm…计蒜客的题还是一如既往的鬼畜
先看数据规模：n<=10^5
这又（？）决定了只能用DP做
诶等等，题面上明明说”可以吃任意颗糖但是不能连续选择三颗及以上的糖来吃”，有后效性，你跟我说用DP？
别急，我会说明白的。
记得某位NOIP教练说：DP不会就加一维。
所以我们要这样定义状态：第一维表示第几颗糖果，第二维表示已经吃了多少糖果。
把已经吃了多少糖果放进状态里，就完美地避开了后效性。
转移方程：
AC代码：
版权声明：本文为tianxing-zhao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。