| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第一个 完完全全 自己推公式 单调队列优化出来的DP,,贴代码纪念!!!//
// 代码可能比较冗余 , 莫拍砖,,学习中 --> _ -->
//
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000011
using namespace std;
typedef struct nn{
int l ,r;
}node;
node crows[1001];
typedef struct QU{
int id ,val;
}QUE;
QUE que[maxn >> 1];
bool cmp(const node a, const node b){
return a.r < b.r; //按照思想检查算法 此处应是按照 牛的右边界排序。。 贡献了几次wa
}
int dp[maxn] ;
int binsearch (int val,int l, int r){ //二分查找 单调队列
int mid;
while(l <= r){
mid = (l + r) >> 1;
if (que[mid].val >= val) //队列数组是升序排列升序,查找第一个比他小的
r = mid -1;
else
l = mid + 1;
}
return r;
}
int main(){
int i ,j ,k ,a ,b ,l ,R ,r ,L ,n ,top ,rear ,index;
QUE temp;
while (~scanf("%d%d",&n ,&L)){
scanf("%d%d",&a,&b);
for (i = 0; i < n ;i ++) scanf("%d%d",&crows[i].l,&crows[i].r);
sort(crows ,crows + n , cmp);
top = rear = 1;
que[1].val = 99999999;
que[1].id = 0;
dp[0] = 0 ;
for (i = 1; i < 2 * a; i ++) dp[i] = -1; //
for (i = 2 * a; i <= L ; i ++ ){
if (i % 2 ) {
dp[i] = -1 ;
continue;
}
if (dp[i - 2 *a] != -1){
index = binsearch(dp[i - 2 * a] ,top ,rear);
temp.id = i - 2 * a ;
temp.val = dp[i - 2 * a]; /// 初始化dp 数组
rear = index + 1;
que[rear] = temp ;
}
while (i - que[top].id > 2 * b && top <= rear) top++;
if (que[top].val == 99999999 || top > rear) dp[i] = -1;
else dp[i] = que[top].val + 1;
} ///
for (i = 0 ;i < n ; i ++) {
R = ( crows[i].r % 2 == 1)? crows[i].r +1 : crows[i].r;
l = crows[i].l;
top = rear = 1;
que[1].val = 99999999;
que[1].id = 0;
for ( j = l + 1 ; j < R ;j ++) dp[j] = -1 ;
for ( j = R - 2 * b < 0 ? 0 :R - 2 * b; j < R - 2 * a; j ++ ) {
if (dp[j] != -1){
index = binsearch(dp[j] ,top ,rear);
temp.id = j;
temp.val = dp[j];
rear = index + 1;
que[rear] = temp ;
}
}
int l1 = L ; //
if (i != n -1 ) // 此三行TLE 后反应过来 的优化
l1 = min (l1 ,crows[ i+ 1].l); //
for ( j = R ; j <= l1 ; j ++) {
if (j % 2 ) {
dp[j] = -1 ;
continue;
}
if (dp[j - 2 *a] != -1){
index = binsearch(dp[j - 2 * a] ,top ,rear);
temp.id = j - 2 * a ;
temp.val = dp[j - 2 * a];
rear = index + 1;
que[rear] = temp ;
}
while (j - que[top].id > 2 * b && top <= rear) top++;
if (que[top].val == 99999999 || top > rear) dp[j] = -1;
else dp[j] = que[top].val + 1;
}
}
printf("%d\n",dp[L]);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator