斜率优化初探：以[HNOI2008]玩具装箱为例记\(f[i]\)表示装好前\(i\)个的最小花费。容易写出转移：\[f[i]=\min_{j\lti}\[f[j]+(s[i]-s[j]-1-L)^2]\]直接转移是\(O(n^2)\)的，我们考虑斜率优化。斜率优化的过程（一）问题转化成了求最小截距。我们把\(min\)

P3195[HNOI2008]玩具装箱\(dp_i\)表示前\(i\)个玩具的最小代价。\(s_i=\sum_{j\lei}c_i+1\)。设\(L'=L+1\)。\(dp_i=\min_{j<i}\{dp_j+(s_i-s_j-L')^2\}\)\(dp_i-s_i'^2+2s_iL'=\min_{j<i}\{dp_j+(s_j'+L)^2-2s_is_j\}\)\(b=y

题目传送门题目大意：给定一个长度为\(m\)且只含\(0\sim9\)的字符串\(s\)，求出所有长度为\(n\)的，只含\(0\sim9\)且不含\(s\)字符串的数量，结果对\(mod\)取模。数据范围：\(n\le10^9,m\le20,k\le1000\)。思路：不难发现和这道题很像，只是\(n\)的数据范围被扩大到

原题链接题解正难则反不可能发生越狱的清空：从左到右，第一个人有m种选择，第二个人为了和前面一个人不一样，有m-1种选择。。。code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constllmod=100003;llqpow(lla,lln){llres=1;while(n

之前学矩阵乘的时候做的题，当时因为不会\(kmp\)搜索一稀里糊涂过去了，现在填个坑。头图是\(Logos\)！P3193[HNOI2008]GT考试题链：洛谷题库题目大意：求有多少个长度为\(n\)的数字串的子串中不包含给出的长度为\(m\)位的串，范围\(n<=1e9\)，$m<=20$。思路：首先考虑DP，令\(

[HNOI2008]玩具装箱题目描述P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为\(1\cdotsn\)的\(n\)件玩具，第\(i\)件玩具经过压缩后的一维长度为

题目：[HNOI2008]GT考试阿申准备报名参加GT考试，准考证号为\(N\)位数\(X_1,X_2…X_n\(0\leX_i\le9)\)，他不希望准考证号上出现不吉利的数字。他的不吉利数字\(A_1,A_2,\cdots,A_m\(0\leA_i\le9)\)有\(M\)位，不出现是指\(X_1,X_2\cdotsX_n\)中没有恰好一段等于\(A_

很难得遇到细节题打码5分钟调试两小时感谢游老师送出的1.5h调试，感激(争取每天用我的代码训练老师的该题能力）细节/思路见注释#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;/*本题细节很多！！！1.注意要把‘0’放进去，否则'1'一直弹不出去，导致答案偏大2

http://www.lydsy.com/JudgeOnline/problem.php?id=10071007:[HNOI2008]水平可见直线TimeLimit: 1Sec  MemoryLimit: 162MBSubmit: 7644  Solved: 2922[Submit][Status][Discuss]Description在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往

首先先写dp方程非常简单\(\mathit{f}_{i}=\min(\mathit{f}_{j}+(\mathit{c}_{i}+i-j-1-L-\mathit{c}_{j})^2)\)(其中\(\mathit{c}_{i}\)表示长度前缀和）然后发现括号

题目：P3195[HNOI2008]玩具装箱 一道斜率优化dp题。先考虑状态和转移方程：令$dp[i]$表示装前$i$个玩具所需要最小花费，$j$表示上一个容器右端点，$sum[i]$表示前$i$个玩具长

先考虑朴素的dp。由于涉及到匹配问题，只有一个串，考虑kmp。状态表示设\(f_{i,j}\)表示长度为\(i\)的字符串，与不吉利串的匹配长度为\(j\)的总方案数。状态转移

[BZOJ1009][HNOI2008]GT考试Description    阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2

StatementLuoguSolution首先考虑最为暴力的做法,也就是我们直接设$f_i$表示将前$i$个玩具合并,那么有转移:$$f_i=\min_{j=1}^{i-1}{f_j+val(j+1,i)}$$这个时候很明

题目链接：​​传送门​​早做过的我们用全部的方案数减去不越狱的方案数全部的方案数就是是宗教数是房间数保证不越狱的话第一个房间的罪犯有种宗教可以选择剩下的个房

原题链接dp+矩阵加速明天再来写#pragmaGCCoptimize(2)#include<bits/stdc++.h>usingnamespacestd;#definefrfirst#definesesecond#defineet0exit(0);#

给定序列\(C\)，将原序列拆成几个部分,每个部分\([i,j]\)费用为\(j-i+\sum^{j}_{k=i}C_k\)，最小化费用。\(n\leq5\times10^4\)。定义\(sum[i]\)为前\(i\)项的