DP灌溉草场

小灰灰 2022-03-19 11:26 191阅读 0赞

题目 ：poj2373

代码：

#include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    const int INFINITE = 1<<30;
    const int MAXL = 1000010;
    const int MAXN = 1010; 
    int F[MAXL]; 
    int cowThere[MAXL];
    int N,L,A,B; 
    struct Fx {
    	int x; 
    	int f;
    	bool operator<(const Fx & a) const { 
    		return f > a.f; 
    	}
    	Fx(int xx=0,int ff=0):x(xx),f(ff) { }
    };// 在优先队列里，f值越小的越优先
    priority_queue<Fx> qFx;
    int main() 
    {
    	cin >> N >> L;
    	cin >> A >> B;
    	A <<= 1; 
    	B <<= 1; //A,B的定义变为覆盖的直径（半径乘于2） 
    	memset(cowThere,0,sizeof(cowThere));
    	for( int i = 0;i < N; ++i ) {
    		int s,e;
    		cin >> s >> e;
    		++cowThere[s+1]; //从s+1起进入一个奶牛区
    		--cowThere[e]; //从e起退出一个奶牛区
    	}
    	int inCows = 0; //表示当前点位于多少头奶牛的活动范围之内
    	for( int i = 0;i <= L ; i ++) { //算出每个点是否有奶牛
    		F[i] = INFINITE;
    		inCows += cowThere[i];
    		cowThere[i] = inCows > 0;//...妙啊！！！ 
    	}//初始化数组 
    
    	for( int i = A;i <= B ; i += 2 ) //初始化队列（一倍小直径和一倍大直径之间 
    		if(! cowThere[i] ) { 
    			F[i] = 1;
    			if( i <= B + 2 - A ) //这句话的意思是  对B+2这个 dp起始点  把所有能影响这个点的坐标入队 
    				qFx.push(Fx(i,1)); 
    		}
    	for( int i = B + 2 ; i <= L; i += 2 ) {
    		if( !cowThere[i] ) { //如果这里没有奶牛（即水龙头边界可以是这个坐标） 
    			Fx fx;
    			while(!qFx.empty()) {//删除不能影响到当前点的队头 
    				fx = qFx.top();
    				if( fx.x < i - B )
    					qFx.pop();
    				else
    					break;
    			}
    			if ( ! qFx.empty() ) //当前点为对头加 1，
    				F[i] = fx.f + 1;
    		}
    		if( F[i + 2 - A] != INFINITE) {//入队一个能影响到下一个点的元素 
    			qFx.push(Fx(i + 2 - A, F[i + 2 - A])); 
    		} 
    	}//dp全过程 一旦出现某个点不能被浇灌到 那么就会断层； 
    	if( F[L] == INFINITE ) //如果不满足条件 
    		cout << -1 <<endl;
    	else 
    		cout << F[L] << endl; //满足条件 
    	return 0;
    } // 复杂度：O(nlogn)