就是给你一堆:
x[i1] >= x[j1] + a[1]
x[i2] >= x[j2] + a[2]
...
x[in] >= x[jn] + a[n]
然后问你有没有解,有解可能还会让你求出一个解的问题
对这个题来说
令a[i] = 1表示i在你选的集合中, a[i] = 0表示i不在
如果令S[i] = a[0] + a[1] + a[2] + ... + a[i]
显然S[i] >= S[i-1]
对应于区间[f,t],里面至少有两个数被选等价于S[t] - S[f-1] >= 2
这样得到一组不等式,问题就是,问有解否,有解的话,求出s[m]的最小值
> 04学长啊，谢啦
> 不过什么是差分约束啊
> 

• Re:尽量选终点和终点的前一个点 (335) cpp0600548202 2006-05-13 17:33:23
  • 差分约束那么快搞懂？！ (23) frkstyc 2006-05-13 17:35:37
    • Re:差分约束那么快搞懂？！ (25) cpp0600548202 2006-05-13 20:57:32