以下的time均为离散化后的结果,保证按照时间正序排列
8/12
time1 抵达上海浦东国际机场,上飞机
time2 我chovy我英语书摘作业没写,直接开干
time3 我去这个东西工作量咋这么大/yi,写了3小时才写 18\frac{1}{8}81 ,不管了接着写
time4 吃饭,玩蛇棋,玩2048
time5 写作业,最终进度 38\frac{3}{8}83
8/13
time6 睡觉
time7 写作业
8/12
东八区的小朋友们想不到吧我又返厂了
time8 落地美利坚合众国德克萨斯州首府达拉斯沃斯堡国际机场,这机场咋这么大
time9 入关,趁机偷偷打一会MC
time10 /yi达拉斯怎么地面温度40度,吓哭了
time11 /yi这个酒店到底怎么过去啊,看着很近的亚子
time12 被家长绕晕了,到底坐哪个车
time13 在巨大停车场中转圈,路上遇到一只巨大蟑螂
time14 抵达酒店
time15 玩MC
time16 好了让我们来写一道题吧
戳我
思考一下不难发现John的最小交付硬币数相当于多重背包,店主的找零相当于完全背包,那么先把这几个求出来,但是John多付一些钱去找零的方案可以更优,所以先把背包上界开到 500005000050000 试试(更大害怕会T),最后统计结果是取付钱的最少硬币数+找零的最小硬币数的最小值。
time17 先睡,躺在床上胡了半天背包上界值的求法(求出 244002440024400,好像是对的),花费半小时最后才搞出一个诡异的抽屉原理证法(太模糊不放了),我咋这么弱。
8/13
time18 我怎么4点就醒了/yi
time19 睡不着起床
time20 实现代码并通过此题,为什么 101001010010100 的上界能过!?数据水炸了
Code
time21 早饭好吃喵
time22 发现了续期稳的座右铭,没绷住
time23 玩MC
time24 好了让我们来写一道题吧
戳我
由于 k≤8k\leq8k≤8 所以考虑状压DP,套一个背包求方案数,怎么做完了?这题真这么简单?
time25 调了半天红温了,遂前往机场
time26 落地佛罗里达州奥兰多国际机场
time27 到酒店,去奥兰多迪士尼Magical Kingdom,以为烟火是9点的结果是十点的,气炸了。
8/14
time28 去奥兰多迪士尼Animal Kingdom,阿凡达的项目很好玩。
time29 去奥兰多迪士尼Magical Kingdom看烟火,今天是万圣节活动,游行和城堡阴完了,看到了烟火但是也很阴。
8/15
time29 去奥兰多迪士尼Epcot,这园中的大湖周围怎么是万国博览会,小湖周围一般是巨刺激的项目一半是各种大学习
time30 溜去旁边的HollyWood Studio,玩了两个星战相关的项目,坐船滚回Epcot
time31 Epcot湖上的烟火>>>>>>>>>>Magical Kingdom城堡的烟火
8/16
time32 参观卡纳尔维拉尔角肯尼迪航天中心,喝了两杯可乐。
time33 去机场飞DC华盛顿
time34 写一下做题计划里的题(P1117)
time35 跟复仇者x对线
8/17
time36 去超市买点东西
time37 写了两道题(P13323,P14347),我在后者竟然不经过调试连续完成了通过编译,通过样例,AC。
P13323本质上是一个最长公共子序列,将每一个段作为整体求最长公共子序列,但是需要把前面的段内别的可以匹配的放进来,Code。
P14347在最优状态下有几个重要结论:区间覆盖操作不相交,区间翻转操作不相交,先区间覆盖再区间翻转一定不劣,具体证明看题解,这里就不写了。
然后定义 dpi,0,0dp_{i,0,0}dpi,0,0 表示为当前第 iii 位,这一位不覆盖,不翻转;dpi,0,1dp_{i,0,1}dpi,0,1 表示为当前第 iii 位,这一位不覆盖,翻转;dpi,1,0dp_{i,1,0}dpi,1,0 表示为当前第 iii 位,这一位覆盖为0,不翻转;dpi,1,1dp_{i,1,1}dpi,1,1 表示为当前第 iii 位,这一位覆盖为0,翻转;dpi,2,0dp_{i,2,0}dpi,2,0 表示为当前第 iii 位,这一位覆盖为1,不翻转;dpi,2,1dp_{i,2,1}dpi,2,1 表示为当前第 iii 位,这一位覆盖为1,翻转。
转移时如果第二维或第三维不为 000 且与 i−1i-1i−1 的这一维状态不同则需要在前一位基础上加一,具体实现见代码,Code。
time38 忙一些私事
8/18
time39 坐火车去纽约,火车上写作业写题
time40 到车站直接去帝国大厦
time41 穿过第五大道和时代广场去酒店