将ZOJ的差分约束差不多刷完了，题型都很类似（具体差分约束介绍 hit），除了1420有点变种导致有点儿棘手，还有就是2049恐怖的数据范围。
基本题型：
给出一个序列，1至n这n个数字，然后已知从 i 到 j 的数字和至多a、至少b，给出这么一 组，然后求每个数字最小为多少，或者求总和最小为多少。
于是构造，设s[i]为0到i的和，那么s[1]即为第一个数字，s[2]-s[1]即为第二个数字，于是给出的条件转换为：
s[i] - s[j] >= b
s[i] - s[j] <= a
s[i] - s[i-1] >= 0
s[i] - s[i-1] <= V （*如果是1到n这n个容器，每个容器有容量，或者特殊情况n个布尔值，那么需要加上这个限制条件）
下面介绍这6道题，基本是我认为的由易至难吧：
ZOJ - 1508 Intervals
本题算是比较直接的差分约束了（总不能真的是二元不等式吧）。题目大意：
给出一些区间[ai,bi]和每个区间最少需要几个点ci，然后问总共最少需要几个点满足所有区间的要求。比如给出1 5 2和 4 6 2，就是说1到5需要2个点，4到6需要2个点，那么最少需要2个点就可以满足条件了。
这个就是上面说的布尔值了，抽象成s[bi] - s[ai-1] >= ci 以及 s[i] - s[i-1] >= 0 和 s[i] - s[i-1] <= 1，然后进行差分约束求最长路。另外，此题不需要判断是否不满足条件，即存在环。另外，全部初始化为0即可，或者除起始点为0其余点为-Inf，然后松弛的时候判断一下。
ZOJ - 2770 Burn the Linked Camp
本题也是很裸的差分约束。大意：
说刘备将营地都连在了一起，于是陆逊想要估计总共有多少人，所以就侦察到了每个营地的容量，即最多有多少士兵，又估计了一下从 i营地 到 j营地最少有多少士兵，求总共最少有多少人，或者估计有误（即出现了正负环）。
等效：s[i] - s[j - 1] >= k, s[i] - s[i-1] >= 0 ，且 s[i] - s[i-1] <= Ci （即有容量限制）。
初始化：全为0即可，或者除起始点为0其余点为-Inf，然后松弛的时候判断。
ZOJ - 1260 King
本题再上面两题加了一点变化就是：取消了等于号，于是需要+1或者-1处理。题意：
国王生了个傻儿子，只会算从 s 开始厚n 个数的和大于或者小于k。他给出一组si、ni、ki,让你去判断是否存在这样的数。
等效：d[si + ni] - d[ni - 1] >= k + 1 和 d[si + ni] - d[ni - 1] <= k - 1。无容量限制。
初始化：因为仅需要判断是否存在，于是全部初始化为0（随意取相同值）即可。
ZOJ - 1455 Schedule Problem
本题不同于上面3道题，但是也很简单可以构造出不等式。题意：
有很多任务，不同任务直接有4种关系： FAS, FAF, SAF or SAS （F代表Finish，A代表After，S代表Start）。求问如何安排这些任务（输出每个任务的开始时间）。
于是以每个任务开始时间列不等式关系：
SAF a b s[a] - s[b] >= e[b]
FAF a b s[a] - s[b] >= e[b] - e[a]
SAS a b s[a] - s[b] >= 0
FAS a b s[a] - s[b] >= -e[a]
（XAY a b代表a X A b Y）
初始化：全部初始化为0，或者将任务1初始化为0，其余-Inf。
ZOJ - 2049 Advertisement
本题也是属于前三个那种区间求和之类的，跟1有点儿类似，不知道为什么AC的人这么少。
题意：
有一条路，人们经常在这里慢跑，但是不同的人慢跑区间不同。广告公司想在这里给公司做广告，但是这个公司要求保证，每个人必须注意到K次这个广告（即这个区间里面有K个广告牌），但是如果这个人比较懒，跑的区间本身比K小，那么需要这个懒汉区间的所有部分都有广告牌。
构造：由于有负数，不利于数组操作，于是加一个Base(10000)上去。于是对于每个慢跑的人，假如其区间为 a 到 b，而且长度大于k，那么构造：s[b] - s[a-1] >= k；但是如果a到b的长度小于k，那么s[i] - s[i-1] >= 1, a < i <= b，即a到b区间里每个点都与下一个点连一条权值为1的边。然后对于所有的点（这里需要求出minn和maxn，以确定这个总区间的大小）s[i] - s[i-1] >= 0。
初始化：全部为0即可。
ZOJ - 1420 Cashier Employment
本题在原来的最基础题型上加了一点，那就是变成一个环了。以前从i到j怎么怎么的，都是线性的，现在变成一个环，i到j有边，j到i也有边。我们先看题意：
一个24小时服务的零售店，给出其从0点1点...23点到0点每小时内需要服务员的个数，再给出一些应聘者开始工作的时刻，每个应聘者工作8小时，求最少需要招聘几个服务员就够了。
首先，很容易构造s[i] 为从0点到i点需要的服务员个数，于是s[i] - s[i-1] >= 0, s[i] - s[i-1] < a[i-1]（这里a[i-1]为选择i-1这个时刻开始的应聘服务员个数。我们没必要把它后推到i+7都构造一个，因为我们有下面这个不等式可以保证）， s[i] - s[i - 8] >= r[i-1] （r[i-1]代表i-1到i这一个小时内需要的服务员个数）。因为s[i]代表的是需要服务员的个数，所以s[i]和s[i-8]有这样的关系，即s[i]只能来源于i-1、i-2....i-7这几个时刻延续过来（每个服务员工作8小时），所以比s[i-8]要大r[i-1]。当然这个不等式有个注意的地方就是，它是从9开始的。于是我们的BOSS出来了，如果i在1到8之间那么：s[i + 16] - s[i] >= r[i-1] - s[24]。咦？这里怎么出现了s[24]，s[24]不是我们要求的么？对！这正是纠结的地方。这时候需要枚举s[24]，从小到大，如果不出现正环（如果s[24]不够大，比如会导致s[i+16]到s[i]这条边比较大，于是会出现正环），那么就是答案。
这就是最近学习差分约束的成果：
基本题型：
给出一个序列，1至n这n个数字，然后已知从 i 到 j 的数字和至多a、至少b，给出这么一 组，然后求每个数字最小为多少，或者求总和最小为多少。
于是构造，设s[i]为0到i的和，那么s[1]即为第一个数字，s[2]-s[1]即为第二个数字，于是给出的条件转换为：
s[i] - s[j] >= b
s[i] - s[j] <= a
s[i] - s[i-1] >= 0
s[i] - s[i-1] <= V （*如果是1到n这n个容器，每个容器有容量，或者特殊情况n个布尔值，那么需要加上这个限制条件）
下面介绍这6道题，基本是我认为的由易至难吧：
ZOJ - 1508 Intervals
本题算是比较直接的差分约束了（总不能真的是二元不等式吧）。题目大意：
给出一些区间[ai,bi]和每个区间最少需要几个点ci，然后问总共最少需要几个点满足所有区间的要求。比如给出1 5 2和 4 6 2，就是说1到5需要2个点，4到6需要2个点，那么最少需要2个点就可以满足条件了。
这个就是上面说的布尔值了，抽象成s[bi] - s[ai-1] >= ci 以及 s[i] - s[i-1] >= 0 和 s[i] - s[i-1] <= 1，然后进行差分约束求最长路。另外，此题不需要判断是否不满足条件，即存在环。另外，全部初始化为0即可，或者除起始点为0其余点为-Inf，然后松弛的时候判断一下。
ZOJ - 2770 Burn the Linked Camp
本题也是很裸的差分约束。大意：
说刘备将营地都连在了一起，于是陆逊想要估计总共有多少人，所以就侦察到了每个营地的容量，即最多有多少士兵，又估计了一下从 i营地 到 j营地最少有多少士兵，求总共最少有多少人，或者估计有误（即出现了正负环）。
等效：s[i] - s[j - 1] >= k, s[i] - s[i-1] >= 0 ，且 s[i] - s[i-1] <= Ci （即有容量限制）。
初始化：全为0即可，或者除起始点为0其余点为-Inf，然后松弛的时候判断。
ZOJ - 1260 King
本题再上面两题加了一点变化就是：取消了等于号，于是需要+1或者-1处理。题意：
国王生了个傻儿子，只会算从 s 开始厚n 个数的和大于或者小于k。他给出一组si、ni、ki,让你去判断是否存在这样的数。
等效：d[si + ni] - d[ni - 1] >= k + 1 和 d[si + ni] - d[ni - 1] <= k - 1。无容量限制。
初始化：因为仅需要判断是否存在，于是全部初始化为0（随意取相同值）即可。
ZOJ - 1455 Schedule Problem
本题不同于上面3道题，但是也很简单可以构造出不等式。题意：
有很多任务，不同任务直接有4种关系： FAS, FAF, SAF or SAS （F代表Finish，A代表After，S代表Start）。求问如何安排这些任务（输出每个任务的开始时间）。
于是以每个任务开始时间列不等式关系：
SAF a b s[a] - s[b] >= e[b]
FAF a b s[a] - s[b] >= e[b] - e[a]
SAS a b s[a] - s[b] >= 0
FAS a b s[a] - s[b] >= -e[a]
（XAY a b代表a X A b Y）
初始化：全部初始化为0，或者将任务1初始化为0，其余-Inf。
ZOJ - 2049 Advertisement
本题也是属于前三个那种区间求和之类的，跟1有点儿类似，不知道为什么AC的人这么少。
题意：
有一条路，人们经常在这里慢跑，但是不同的人慢跑区间不同。广告公司想在这里给公司做广告，但是这个公司要求保证，每个人必须注意到K次这个广告（即这个区间里面有K个广告牌），但是如果这个人比较懒，跑的区间本身比K小，那么需要这个懒汉区间的所有部分都有广告牌。
构造：由于有负数，不利于数组操作，于是加一个Base(10000)上去。于是对于每个慢跑的人，假如其区间为 a 到 b，而且长度大于k，那么构造：s[b] - s[a-1] >= k；但是如果a到b的长度小于k，那么s[i] - s[i-1] >= 1, a < i <= b，即a到b区间里每个点都与下一个点连一条权值为1的边。然后对于所有的点（这里需要求出minn和maxn，以确定这个总区间的大小）s[i] - s[i-1] >= 0。
初始化：全部为0即可。
ZOJ - 1420 Cashier Employment
本题在原来的最基础题型上加了一点，那就是变成一个环了。以前从i到j怎么怎么的，都是线性的，现在变成一个环，i到j有边，j到i也有边。我们先看题意：
一个24小时服务的零售店，给出其从0点1点...23点到0点每小时内需要服务员的个数，再给出一些应聘者开始工作的时刻，每个应聘者工作8小时，求最少需要招聘几个服务员就够了。
首先，很容易构造s[i] 为从0点到i点需要的服务员个数，于是s[i] - s[i-1] >= 0, s[i] - s[i-1] < a[i-1]（这里a[i-1]为选择i-1这个时刻开始的应聘服务员个数。我们没必要把它后推到i+7都构造一个，因为我们有下面这个不等式可以保证）， s[i] - s[i - 8] >= r[i-1] （r[i-1]代表i-1到i这一个小时内需要的服务员个数）。因为s[i]代表的是需要服务员的个数，所以s[i]和s[i-8]有这样的关系，即s[i]只能来源于i-1、i-2....i-7这几个时刻延续过来（每个服务员工作8小时），所以比s[i-8]要大r[i-1]。当然这个不等式有个注意的地方就是，它是从9开始的。于是我们的BOSS出来了，如果i在1到8之间那么：s[i + 16] - s[i] >= r[i-1] - s[24]。咦？这里怎么出现了s[24]，s[24]不是我们要求的么？对！这正是纠结的地方。这时候需要枚举s[24]，从小到大，如果不出现正环（如果s[24]不够大，比如会导致s[i+16]到s[i]这条边比较大，于是会出现正环），那么就是答案。
这就是最近学习差分约束的成果：
RSS Feed