• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            hdu3440(差分約束)

            題目網(wǎng)址: http://acm.hdu.edu.cn/showproblem.php?pid=3440 

            House Man

            Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 446    Accepted Submission(s): 157


            Problem Description
            In Fuzhou, there is a crazy super man. He can’t fly, but he could jump from housetop to housetop. Today he plans to use N houses to hone his house hopping skills. He will start at the shortest house and make N-1 jumps, with each jump taking him to a taller house than the one he is jumping from. When finished, he will have been on every house exactly once, traversing them in increasing order of height, and ending up on the tallest house.
            The man can travel for at most a certain horizontal distance D in a single jump. To make this as much fun as possible, the crazy man want to maximize the distance between the positions of the shortest house and the tallest house.
            The crazy super man have an ability—move houses. So he is going to move the houses subject to the following constraints:
            1. All houses are to be moved along a one-dimensional path.
            2. Houses must be moved at integer locations along the path, with no two houses at the same location.
            3. Houses must be arranged so their moved ordering from left to right is the same as their ordering in the input. They must NOT be sorted by height, or reordered in any way. They must be kept in their stated order.
            4. The super man can only jump so far, so every house must be moved close enough to the next taller house. Specifically, they must be no further than D apart on the ground (the difference in their heights doesn't matter).
            Given N houses, in a specified order, each with a distinct integer height, help the super man figure out the maximum possible distance they can put between the shortest house and the tallest house, and be able to use the houses for training.
             

            Input
            In the first line there is an integer T, indicates the number of test cases.(T<=500)
            Each test case begins with a line containing two integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤1000000). The next line contains N integer, giving the heights of the N houses, in the order that they should be moved. Within a test case, all heights will be unique.
             

            Output
            For each test case , output “Case %d: “first where d is the case number counted from one, then output a single integer representing the maximum distance between the shortest and tallest house, subject to the constraints above, or -1 if it is impossible to lay out the houses. Do not print any blank lines between answers.
             

            Sample Input
            3 4 4 20 30 10 40 5 6 20 34 54 10 15 4 2 10 20 16 13
             

            Sample Output
            Case 1: 3 Case 2: 3 Case 3: -1

            // Bellman_Ford 
            #include <stdio.h>
            #include 
            <memory>
            #include 
            <iostream>
            #include 
            <algorithm>
            #include 
            <cstring>
            #include 
            <vector>
            #include 
            <map>
            #include 
            <cmath>
            #include 
            <set>
            #include 
            <queue>
            #include 
            <time.h> 
            #include 
            <limits>
            using namespace std;
            #define typev int
            #define N 1005
            #define inf 0x7fffffff 
            #define E (N*5) 
            const double pi = acos(-1.0); 
            struct e{
                
            int st, ed; 
                typev len;  
                
            void set(int _st, int _ed, typev _len){
                    st 
            = _st; 
                    ed 
            = _ed; 
                    len 
            = _len; 
                }
            }es[E];
            struct node{
                
            int h; 
                
            int i; 
            }nodes[N];
            e
            * fir[N]; 
            int n, en, d;
            int st, ed; 
            int vis[N], t[N], que[N]; 
            typev dist[N]; 
            inline 
            bool cmp(node n1, node n2){
                
            return n1.h < n2.h; 
            }
            inline 
            bool relax(int st, int ed, int len){
                
            if(dist[st] < inf && dist[ed] > dist[st] + len){
                    dist[ed] 
            = dist[st] + len;
                    
            return true
                }
                
            return false
            }
            bool Bellman_Ford(int n, int st){  //返回true表示有負(fù)環(huán)
                int i, j; 
                
            bool flag; 
                
            for(i = 0; i < n; i++) dist[i] = inf; 
                dist[st] 
            = 0
                
            for(i = 0; i < n; i++){
                    flag 
            = false
                    
            for(j = 0; j < en; j++){
                        
            if(relax(es[j].st, es[j].ed, es[j].len)) flag = true
                    }
                    
            if(!flag) break
                }
                
            return flag;  
            }
            int cnt = 0
            int main(){
            #ifndef ONLINE_JUDGE
                freopen(
            "in.txt""r", stdin); 
                
            //freopen("out.txt", "w", stdout); 
            #endif 

                
            int t, i, ans, u, v;
                scanf(
            "%d"&t);
                
            while(t--){
                    scanf(
            "%d%d"&n, &d);
                    
            for(i = 0; i < n; i++){
                        scanf(
            "%d"&nodes[i].h);
                        nodes[i].i 
            = i; 
                    }
                    en 
            = st = ed = 0
                    sort(nodes, nodes
            +n, cmp); 
                    st 
            = nodes[0].i; 
                    ed 
            = nodes[n - 1].i; 
                    
            if(st > ed) swap(st, ed); 
                    
            for(i = 0; i < n; i++) fir[i] = NULL; 
                    
            for(i = 1; i < n; i++){
                        es[en
            ++].set(i, i-1-1); 
                        u 
            = nodes[i].i; 
                        v 
            = nodes[i - 1].i; 
                        
            if(u < v){
                            es[en
            ++].set(u, v, d); 
                        }
            else es[en++].set(v, u, d); 
                    } 
                    
            if(!Bellman_Ford(n, st)) ans = dist[ed];
                    
            else ans = -1
                    printf(
            "Case %d: %d\n"++cnt, ans);

                }
                
            return 0;
            }



            posted on 2011-01-23 01:13 tw 閱讀(496) 評(píng)論(0)  編輯 收藏 引用 所屬分類: HDU題解

            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿

            文章分類

            文章檔案

            搜索

            最新評(píng)論

            国产精品天天影视久久综合网| 久久不射电影网| 亚洲伊人久久综合中文成人网| 久久亚洲天堂| 久久久噜噜噜www成人网| 国产日产久久高清欧美一区| 久久精品亚洲乱码伦伦中文| 久久强奷乱码老熟女网站| 丁香狠狠色婷婷久久综合| 久久综合久久伊人| 久久久久亚洲精品无码蜜桃| 久久精品国产精品亚洲下载 | 无码日韩人妻精品久久蜜桃 | 好属妞这里只有精品久久| 91精品国产综合久久香蕉| 久久只这里是精品66| 青青草国产精品久久久久| 精品国产99久久久久久麻豆| 草草久久久无码国产专区| 久久久久久亚洲精品成人| 欧美日韩成人精品久久久免费看 | 色欲久久久天天天综合网| 久久婷婷五月综合成人D啪| 精品蜜臀久久久久99网站| 人妻无码精品久久亚瑟影视 | 色婷婷久久综合中文久久蜜桃av| 99久久精品国产综合一区| 久久精品aⅴ无码中文字字幕不卡| 久久久久亚洲AV无码专区桃色| 成人国内精品久久久久影院| 亚洲AV无码久久精品色欲| 色婷婷狠狠久久综合五月| 久久婷婷色综合一区二区| 久久久WWW成人免费精品| 国产亚洲成人久久| 国内精品久久久久影院免费| 久久婷婷五月综合97色一本一本| 99久久国产精品免费一区二区| 伊人 久久 精品| 久久综合视频网| 日本人妻丰满熟妇久久久久久|