• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0

            題目的意思是給出含有n(n<=10000)個數字的序列,從序列中選取m(m<=100)個數字,任意兩個相鄰的數字的位置差不能小于k,求m個數字的最大值。

            考試的時候沒有想到用動態規劃,只想到了一種貪心,每次選取最大的那個數字,查看如果選取它是不是和已經選取的發生沖突,如果不沖突,則選取,否則繼續下一個最大的數字。考試時不是沒有向動態規劃的方向考慮過,而是想到如果定義d[i][j]為第i次選取第j個數字獲得的最大值,那么算法的時間復雜度是O(mn^2),肯定超時!

            考完試仔細思考,如果定義d[i][j]為第i次選取前j個數字獲得的最大值,時間復雜度不就是O(mn)了嗎!怎么考試的時候沒有想到!這樣一來,狀態轉移方程如下:d[i][j]=max(d[i][j-1],d[i-1][j-k]+a[j])。對于每一個確定的i,j都有一個取值范圍,(i-1)*k+1<=j<=n-(m-i)*k。同時需要注意(i-1)*k+1==j時,必須要選取當前數字,因為需要在編號1—j的數字中選擇i個數字。使用滾動數組的技巧,可以把空間復雜度優化到O(n)。

            我的代碼如下:

            #include<stdio.h>
            #define max(a,b) (a>b?a:b)
            long n,m,k,i,j,a[10088],d[2][10088]={0};
            int main()
            {
                FILE 
            *fin,*fout;
                fin
            =fopen("bright.in","r");
                fscanf(fin,
            "%ld%ld%ld",&n,&m,&k);
                
            for(i=1;i<=n;i++)
                  fscanf(fin,
            "%ld",&a[i]);
                fclose(fin);
                
            // Read In
                d[0][1]=a[1];
                
            for(i=2;i<=n;i++)
                  d[
            0][i]=max(a[i],d[0][i-1]);
                
            for(i=2;i<=m;i++)
                  
            for(j=(i-1)*k+1;j<=n-(m-i)*k;j++)
                    
            if(j==(i-1)*k+1) d[(i+1)%2][j]=d[i%2][j-k]+a[j];
                    
            else d[(i+1)%2][j]=max(d[i%2][j-k]+a[j],d[(i+1)%2][j-1]);
                
            // DP
                fout=fopen("bright.out","w");
                fprintf(fout,
            "%ld\n",d[(m+1)%2][n]);
                fclose(fout);
            return 0;
            }

            posted on 2010-01-06 20:08 lee1r 閱讀(198) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:動態規劃
            久久无码AV一区二区三区| 国产精品美女久久久久久2018| 国产美女亚洲精品久久久综合| 久久久久亚洲精品中文字幕| 区久久AAA片69亚洲 | 久久精品免费一区二区| 久久AV高清无码| 欧美粉嫩小泬久久久久久久| 日韩中文久久| 久久99国产精品久久99果冻传媒| 久久青青草原亚洲av无码| 久久青青草原精品国产| 久久无码国产| 久久婷婷五月综合成人D啪| 国产69精品久久久久777| 一本色道久久88—综合亚洲精品| 香蕉久久一区二区不卡无毒影院| 欧美色综合久久久久久| 久久久精品久久久久特色影视| 久久久久成人精品无码中文字幕| 亚洲乱码日产精品a级毛片久久| 久久久久久久97| 久久99精品国产麻豆| 色诱久久久久综合网ywww| 久久66热人妻偷产精品9| 欧洲成人午夜精品无码区久久 | 国产午夜精品理论片久久影视| 国产精品久久久久久久久软件| 久久热这里只有精品在线观看| 亚洲日韩欧美一区久久久久我 | 久久精品免费一区二区| 香蕉久久夜色精品升级完成| 久久人人爽人人爽人人AV东京热 | 亚洲AV无码一区东京热久久| 人妻无码精品久久亚瑟影视 | 久久精品国产只有精品2020| 色综合久久天天综合| 思思久久99热免费精品6| 国产亚洲综合久久系列| 亚洲综合久久夜AV | 久久久久亚洲av毛片大|