• <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>

            A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)


            有很多細(xì)節(jié)不好考慮,應(yīng)該是我的水平原因。最后我向updog要了數(shù)據(jù)才過(guò)的。而且代碼寫的不好。將就看一下吧。

            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2000-9-10 14:03:51
            File Name: pku3375.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <iostream>
            using namespace std;

            #define out(x) (cout << #x << ": " << x << endl)
            typedef 
            long long int64;
            const int maxint = 0x7FFFFFFF;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template 
            <class T> void show(T a, int n) for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
            template 
            <class T> void show(T a, int r, int l) for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

            const int maxm = 100010;

            int n, m;
            int interface[maxm];
            int computer[maxm];
            int f[2][maxm];
            int last[2];

            int main()
            {
                
            while (scanf("%d%d"&m, &n) != EOF)
                
            {
                    
            for (int i = 1; i <= m; i++)
                        scanf(
            "%d"&interface[i]);
                    
            for (int i = 1; i <= n; i++)
                        scanf(
            "%d"&computer[i]);
                    
                    sort(
            interface + 1interface + 1 + m);
                    sort(computer 
            + 1, computer + 1 + n);

                    
            for (int i = 0; i <= m; i++)
                        f[
            1][i] = maxint;

                    
            for (int i = 0; i <= m; i++)
                        f[
            0][i] = 0;

                    last[
            0= 0;

                    
            for (int i = 1; i <= n; i++)
                    
            {
                        
            int l = 1;
                        
            int r = m;
                        
            while (l + 1 < r)
                        
            {
                            
            int mid = (l + r) / 2;
                            
            if (interface[mid] >= computer[i])
                                r 
            = mid;
                            
            else
                                l 
            = mid;
                        }

                        
            int st = max(l - n - 11);
                        
            int ed = min(l + n + 1, m);
                        
            int now = i % 2;
                        
            int prev = (i + 1% 2;
                        last[now] 
            = ed;
                        
            for (int j = st; j <= ed; j++)
                        
            {
                            
            if (f[prev][j - 1!= maxint)
                                f[now][j] 
            <?= f[prev][j - 1+ abs(computer[i] - interface[j]);
                            
            else if (last[prev] < j - 1)
                                f[now][j] 
            <?= f[prev][last[prev]] + abs(computer[i] - interface[j]);
                            f[now][j] 
            <?= f[now][j - 1];
                        }

                        
            for (int j = 0; j <= m; j++)
                            f[prev][j] 
            = maxint;
                    }

                    
            int ans = maxint;
                    
            for (int i = 0; i <= m; i++)
                        ans 
            <?= f[n % 2][i];

                    printf(
            "%d\n", ans);
                }

                
            return 0;
            }
            posted on 2007-09-11 22:28 Felicia 閱讀(822) 評(píng)論(1)  編輯 收藏 引用 所屬分類: 動(dòng)態(tài)規(guī)劃
            Comments
             
            国产成人无码精品久久久免费 | 亚洲AV无码久久精品色欲| 2021久久国自产拍精品| 欧美亚洲国产精品久久| 欧美精品丝袜久久久中文字幕| 亚洲精品国产成人99久久| 99精品国产在热久久无毒不卡| 亚洲精品美女久久777777| 欧美日韩久久中文字幕| 一本久久免费视频| 亚洲精品国产第一综合99久久| 久久激情亚洲精品无码?V| 国产免费久久精品99久久| 国内精品久久久久影院网站| 青青草原综合久久| 国产精品一区二区久久精品无码| 一级做a爰片久久毛片16| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 亚洲AV乱码久久精品蜜桃| 亚洲AV无码久久精品成人| 亚洲精品乱码久久久久久蜜桃图片| 久久久久久久久久久精品尤物 | 亚洲中文字幕无码久久2017| 99久久国产综合精品女同图片| 亚洲综合伊人久久大杳蕉| 69国产成人综合久久精品| 伊人久久精品线影院| 久久久久国产视频电影| 香蕉99久久国产综合精品宅男自| 热99RE久久精品这里都是精品免费 | 狠狠色丁香婷婷久久综合| 亚洲香蕉网久久综合影视| 国产精品一区二区久久不卡 | 久久亚洲av无码精品浪潮| 精品伊人久久久| 国产精品久久久久AV福利动漫| 国产激情久久久久影院小草| 色播久久人人爽人人爽人人片AV| 久久夜色精品国产噜噜噜亚洲AV| 亚洲成色999久久网站| 欧美久久久久久|