Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

不需要线段树,类似DP的思想,加一个队列表示层次。

Posted by 2742195759 at 2015-11-23 20:22:24 on Problem 2374
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define mod 10e9+7;
#define inf 0x3f3f3f3f
#define mem0(x , y)  memset(x , y , sizeof(x))
using namespace std;
const int MAX = 55000 ;
const int MAXL = 100505 ;
int data[MAX][2] ;
int dp[MAXL*2] ;
int vis[MAXL*2] ;
int main(){
    ///freopen("input" , "r" ,stdin) ;
    int n , s ;
    int a , b ;
    scanf("%d%d",&n,&s) ;
    s += MAXL ;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a,&b) ;
        data[i][0] = a + MAXL ; data[i][1] = b + MAXL;
    }
    mem0(dp , inf) ;
    queue <int> que ;
    que.push(s) ; dp[s] = 0 ;vis[s] = 1 ;
    for(int i=n;i>=1;i--){
        int k = que.size() ;
        while(k --){
            int now = que.front() ; que.pop() ; vis[now] = 0 ;
            if(now <= data[i][0] || now >= data[i][1]) {
                if(!vis[now]){
                    que.push(now) ; vis[now] = 1;
                }
            }
            else {
                dp[data[i][0]] = min(dp[data[i][0]] , dp[now] + abs(now-data[i][0]))  ;
                dp[data[i][1]] = min(dp[data[i][1]] , dp[now] + abs(now-data[i][1]))  ;
                dp[now] = inf ;
                if(!vis[data[i][0]])
                {
                    que.push(data[i][0]) ;
                    vis[data[i][0]] = 1 ;
                }
                if(!vis[data[i][1]]){
                    que.push(data[i][1]) ;
                    vis[data[i][1]] = 1 ;
                }

            }
        }
    }
    int ans = inf ;
    while(!que.empty()){
        int now = que.front() ; que.pop() ;
        ans = min(dp[now] + abs(now-MAXL) , ans ) ;
    }
    printf("%d\n",ans ) ;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator