BZOJ 1010 玩具装箱
题意 有n件玩具，玩具长度为ci。连续的玩具可以装进同一容器里，玩具之间要留有1个单位的空间。容器制作费为(X-L)^2，其中X表示容器长度，L表示常量。求最小费用。 数据范围 $$n\leq50000\ \ \ ;\ \ \ L,C_i\leq10^7$$ 题解 动规方程 根据题目描述很容易列出动规方程： 其中 $$s[i]=\sum_{k=1}^{i} c[k]；$$ 而X即为s
标签：心的开始
半平面交（三弹连发）
半平面交基本概念 半平面：由不等式ax+by+c>=0确定。 在一个有界区域里半平面或半平面的交是一个凸多边形区域。 n个半平面的交是一个至多n条边的凸多边形。BZOJ 1007 水平可见直线 题意 平面直角坐标系上，有n条直线，从y为正无穷处往下看。问能看看到哪些直线？数据范围 $$n\leq50000$$题解 当一条直线不是最后半平面交的组成部分，仅当它被与它斜率相同的直线挡住，或被
BZOJ 1006 神奇的国度
题意 保证大于3人的朋友关系一定会出现弦边（即连接环上不相邻的两个点）。在分组时要求朋友关系的两人不能分在同一组，求最少分几组。 数据范围 $$人数n\leq10000\ \ \ ;\ \ \ 朋友对数m\leq1000000$$ 题解 环上有弦被称为弦图，那这道题就是在弦图上做最小染色（即相邻的点不能染同一种颜色），需要用到完美消除序列的最大势算法(MCS)。最大势算法是排序时每次找势能最大的点
BZOJ 1296 粉刷匠
题意 n条木板，每条木板上有m个格子，每个格子有目标颜色0或1。一次可以粉刷连续若干格，每格只能被粉刷一次。T次粉刷后最多有多少格子颜色正确。（初始无颜色） 数据范围 $$n,m\leqslant50\ \ \ ;\ \ \ T\leqslant2500$$ 题解 泛化背包很久以前就讲过，但一直没有练过，今天是第一次。按照泛化背包的理解，每次先DP一行的状态，求出每一行粉刷i次的答案，再DP所有行
BZOJ 3505 数三角形
题意 在n*m的网格中有多少个顶点在网格上的三角形 数据范围 $$n,m\leqslant1,000$$ 题解 n*m个点中任选三个有C(n+m,3)种选择，在同一行的或同一列的直接算组合数减。对于斜线上的点，有如下做法： (x,y)和(a,b)所成线段中的点数共有gcd(x-a,y-b)+1个（包括两端）。 现在把端点坐标减去(a,b)，就成了(x,y)与(0,0)所成线段，那么长度相同的线
BZOJ 1013 球形空间产生器
题意 给定n维球上n+1个点的坐标，求球心坐标（保证有解） 数据范围 $$n\leqslant10$$ 题解 第一次写高斯消元，历经坎坷终于解决了。已知球上点坐标(x_1,x_2…x_n)，球心坐标为(a_1,a_2…a_n),那就有：$$(x_1-a_1)^2+…+(x_n-a_n)^2=x_1^2-2x_1a_1+a_1^2+…+x_n^2-2x_na_n+a_n^2=r^2$$我们可以写出n