轉自：優YoU??http://user.qzone.qq.com/289065406/blog/1307063918
大致題意：
給出數軸上的n個區間[ai，bi]，每個區間都是連續的int區間。
現在要在數軸上任意取一堆元素，構成一個元素集合V
要求每個區間[ai，bi]和元素集合V的交集至少有ci不同的元素
求集合V最小的元素個數。
?
解題思路：
設s[x] = 從0 到x 的所有在集合中的數的個數
則ai到bi的個數即S[bi] - S[ai-1]。
因此有
(1) S[bi] - S[ai-1] >= ci。
又根據s[x]本身的性質，后面的一定不比前面的小，后面的最多比前面多一，有：
(2) ?s[i + 1] - s[i] >= 0?
(3) ?s[i + 1] - s[i] <= 1
故建圖,使圖中每一組邊，均滿足（注意三條式子的不等號方向要一致，這個很重要）:
S[ai - 1] <= S[bi] - ci?
S[i] <= S[i - 1] + 1?
S[i - 1] <= S[i]
上面三式，可把s[x]看作源點（假設存在）到各點的最短距離，初始化為0；
常數為邊(ai – 1，bi)的邊權
當存在不滿足這三條式子的邊時，對這條邊進行Relax操作，更新不等號左邊的變量。
其實就是Bellman-Ford算法的核心部分
if( S[ai - 1] > S[bi] – 2 )?? S[ai - 1] = S[bi] – ci ；
if( S[i] > S[i - 1] + 1 )?? S[i] > S[i - 1] + 1 ；
if( S[i - 1] > S[i] )?? S[i - 1] = S[i] ；
?
最后源點到最大頂點的距離減去源點到最小頂點的距離就是所求（其實一個單位距離就代表V中的一個元素；最小頂點到最大頂點其實就是所有輸入的區間中，最小的左端點到最大的右端點這個范圍）
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 #include <iostream> 6 #include <map> 7 #include <queue> 8 #include <stack> 9 #include <cmath> 10 //#pragma comment(linker, "/STACK:102400000,102400000") 11 using namespace std; 12 #define PF(x) cout << "debug: " << x << " "; 13 #define EL cout << endl; 14 #define PC(x) puts(x); 15 typedef long long ll; 16 #define CLR(x, v) sizeof (x, v, sizeof(x)) 17 using namespace std; 18 const int INF = 0x5f5f5f5f; 19 const int N= 2e5 + 10; 20 const int mod=1e9 + 7; 21 const int maxn = 5e4 + 10; 22 int n,c[maxn],dis[maxn]; 23 struct st{ 24 int s,e; 25 }val[maxn]; 26 int main() 27 { 28 // freopen("in.txt","r",stdin); 29 while(~scanf("%d",&n)){ 30 int sta = INF,to = 0; 31 for(int i = 1;i <= n;i++){ 32 scanf("%d%d%d",&val[i].s,&val[i].e,&c[i]); 33 val[i].e++; 34 to = max(to,val[i].e); 35 sta = min(sta,val[i].s); 36 } 37 for(int i = 0;i <= n;i++) dis[i] = 0; 38 bool fg = false; 39 while(!fg){//注意不等式的變換，全部是變小 40 fg = true; 41 // cout<<1<<endl; 42 for(int i = 1;i <= n;i++) 43 if(dis[val[i].s] > dis[val[i].e] - c[i]){ 44 fg = false; 45 dis[val[i].s] = dis[val[i].e] - c[i]; 46 } 47 for(int i = sta;i < to;i++) 48 if(dis[i + 1] > dis[i] + 1){ 49 fg = false; 50 dis[i + 1] = dis[i] + 1; 51 } 52 for(int i = to - 1;i >= sta;i--) 53 if(dis[i] > dis[i + 1]){ 54 fg = false; 55 dis[i] = dis[i + 1]; 56 } 57 58 //cout<<dis[to] - dis[sta]<<endl; 59 60 } 61 cout<<dis[to] - dis[sta]<<endl; 62 } 63 return 0; 64 }
?
)
