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