题目链接https://www.luogu.org/problemnew/show/P4302 分析很明显一道区间DP题,对于区间$[l,r]$的字符串,如果它的字串是最优折叠的,那么它的最优结果要么是所有分割出的字串最优结果之和,要么是在断点处恰好有这个区间的周期串可以进行折叠,折叠后产生的结果 状态转移 123456789101112for(ri len=2;len<=n;len++)&
题目链接https://www.luogu.org/problemnew/show/P1005 分析忽然发现这篇题解好像并没有什么意义。。。因为跟奶牛零食那道题一模一样，博主比较懒如果您想看题解的话去区间DP标签中找奶牛零食那道题吧，实在抱歉。。。 话说NOIP喜欢考奶牛题啊(e.g. NOIP2017 D1T1),USACO刷完是不是就能阿克了呀 代码没写高精用__int128代替,话说什么时候
题目链接https://www.luogu.org/problemnew/show/P4677 分析这道题方法跟之前题不一样,我们相当于枚举一个左右端点来线性扩展,同时划分断点进行决策 $f[i][j]$表示在前$i$个村庄中建立$j$个小学的最小距离总和 我们将枚举到第$i$个村庄作为阶段,修了$j$所小学作为状态,通过枚举断点$k$来分割第$j$所小学与前$j-1$所小学 也就是说我们判断$f
题目链接https://www.luogu.org/problemnew/show/P2858 一句话题意: https://cn.vjudge.net/problem/POJ-3186#author=Re0 分析很显然这道题是不行滴,但是把这个数列看作从一个个区间倒着向外扩展取数而成的话,这样就保证了最优子结构和无后效性两个特点,于是就开始DP了 按照区间DP一贯的套路,先初始化元区间,也就是长
题目链接https://www.luogu.org/problemnew/show/SP703 方法一分析很显然可以用一个四维的状态$f[n][a][b][c]$表示完成第i个任务时且三人位置在$a,b,c$时的答案,枚举那个人到达下个位置来状态转移 然而,三人之必须有一个人在$pos[n]$,这个位置 于是我们就枚举前两人的位置$f[n][a][b]$,枚举下谁在$pos[n]$这个位置然后
题目链接https://www.luogu.org/problemnew/show/P1156 方法1分析将已经爬的高度看作背包容积,最大剩余血量看作价值,$f[i][j]$表示吃完第$i$个垃圾,爬到$j$高度的最大剩余血量 $f[i][j+h[i]]=max(f[i][j+h[i]],f[i-1][j]-(t[i]-t[i-1]))$ $f[i][j]=max(f[i][j],f[i-1][j
题目链接https://www.luogu.org/problemnew/show/CF336C 分析一个比较妙的贪心 我们要让最后$and$起来的数被$2^k$整除且$k$最大,我们不妨从后往前枚举$k$,同时运用贪心的思路,对于二进制第$k$为1的数,我们想让最后得到的数除第$k$位外都为0,当然是$and$越多越好 代码123456789101112131415161718192021222
题目链接https://www.luogu.org/problemnew/show/UVA10140 分析$L,R$都很大,显然不能直接筛出$L,R$区间中的质数,这里需要一个结论 结论任何一个合数$N$必定含有一个小于等于$\sqrt N$的质因子 证明反证法,若所有质因子都大于$\sqrt N$,那么无论怎么组合显然都大于$N$ 于是通过这个结论筛出$[2,\sqrt R]$,中的所有素数,把
题目链接https://www.luogu.org/problemnew/show/P2261 分析显然$k$ $mod$ $i=k-\lfloor {k/i}\rfloor$ $\times$ $i$,于是我们只需要求$N * k-\sum_{i=1}^N {\lfloor {k/i}\rfloor\times i}$ 这里就需要数论分块,也称作整除分块的知识 结论:$\forall{i} \i