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

            這是一道NOIp07年的原題,題目本身并不難。

            題目看上去很熟悉,第一次看完題目后往貪心的方面去想的,設(shè)計了兩種貪心策略:1、每次從兩端選取最小的數(shù)字;2、從后向前倒推,使最后一次取到的數(shù)字最大。兩種貪心是不同的,而且都是錯的,競賽原題中給的樣例數(shù)據(jù)都過不去。但是如果不會DP的話,感覺上第二種貪心更易導(dǎo)致最優(yōu)解(只是感覺)。

            動態(tài)規(guī)劃:分析出實(shí)際上行與行之間是互不影響的,就是說對每行的決策可以單獨(dú)進(jìn)行。給定一個區(qū)間[i,j],每次可能的決策是選擇a[i]或者a[j],這樣一個區(qū)間被分成了更小的一部分,考慮動態(tài)規(guī)劃。容易寫出狀態(tài)轉(zhuǎn)移方程:d[i][j]=max(d[i+1][j]+w[i],d[i][j-1]+w[j]),其中w[i]可以很容易推出來,不再給出。

            此題需要注意的地方:1、需要預(yù)處理2^n,因?yàn)橐欢啻斡玫剑?、要用高精度,高精度一般用得比較少,一開始我是把高精度結(jié)果按返回值處理,出了錯;后來改成傳記錄結(jié)果的地址,在高精度函數(shù)中直接修改數(shù)值,第8、9兩個點(diǎn)超時;分析了原因之后,發(fā)現(xiàn)是高精度時傳遞加數(shù)和乘數(shù)耗了太多時,就把加數(shù)、乘數(shù)、結(jié)果全部地址傳遞,vijos上全部數(shù)據(jù)9ms。導(dǎo)致我對于一直沒有太多注意的高精度感慨萬千。

            以下是我的代碼:

            #include<stdio.h>
            #define size 81
            #define max(a,b) (a>b?a:b)
            typedef 
            struct
            {
                
            int len;
                
            long s[30];
            }
            high;
            int n,m,a[size][size]={0};
            high d[
            120][120],Two_[size];
            high zero
            ={1,{0}},one={1,{1}},two={1,{2}};
            void add(high *c,high *a,high *b)
            {// 高精度加上高精度 
                int l,i;
                l
            =(a->len>b->len?a->len:b->len);
                
            for(i=0;i<=l;i++)
                  c
            ->s[i]=0;
                
            for(i=0;i<l;i++)
                
            {
                   c
            ->s[i]+=a->s[i]+b->s[i];
                   
            if(c->s[i]>=100000)
                   
            {
                      c
            ->s[i+1]++;
                      c
            ->s[i]%=100000;
                   }

                }

                c
            ->len=l;
                
            if(c->s[c->len]!=0) c->len++;
            }

            void mul(high *c,high *a,long b)
            {// 高精度乘上單精度 
                int i;
                
            for(i=0;i<=a->len;i++)
                  c
            ->s[i]=0;
                
            for(i=0;i<a->len;i++)
                
            {
                   c
            ->s[i]+=a->s[i]*b;
                   
            if(c->s[i]>=100000)
                   
            {
                      c
            ->s[i+1]+=c->s[i]/100000;
                      c
            ->s[i]%=100000;
                   }

                }

                c
            ->len=a->len;
                
            if(c->s[c->len]!=0) c->len++;
            }

            int high_max(high *a,high *b)
            {// 比較單精度數(shù) 
                long i;
                
            if(a->len>b->len) return 1;
                
            if(a->len<b->len) return 0;
                
            for(i=a->len-1;i>=0;i--)
                  
            if(a->s[i]>b->s[i])
                    
            return 1;
                  
            else if(a->s[i]<b->s[i])
                    
            return 0;
                
            return 1;
            }

            void print(high *a)
            {// 輸出高精度 
                int i;
                printf(
            "%ld",a->s[a->len-1]);
                
            for(i=a->len-2;i>=0;i--)
                
            {
                   
            if(a->s[i]<10000) printf("0");
                   
            if(a->s[i]<1000) printf("0");
                   
            if(a->s[i]<100)   printf("0");
                   
            if(a->s[i]<10)    printf("0");
                   printf(
            "%ld",a->s[i]);
                }

                printf(
            "\n");
            }

            void init()
            {// 打開文件 讀入 預(yù)處理2^n 初始化表 
                int i,j;
                scanf(
            "%ld%ld",&n,&m);
                
            for(i=1;i<=n;i++)
                  
            for(j=1;j<=m;j++)
                    scanf(
            "%ld",&a[i][j]);
                Two_[
            0]=one;
                Two_[
            1]=two;
                
            for(i=2;i<=m;i++)
                  mul(
            &Two_[i],&Two_[i-1],2);
                
            for(i=0;i<=m;i++)
                  
            for(j=0;j<=m;j++)
                    d[i][j]
            =zero;
            }

            high dp(
            int nn)
            {// 對第 nn 行動態(tài)規(guī)劃 
                int i,j;
                high t1,t2,t3,t4;
                
            for(j=0;j<=m-1;j++)
                  
            for(i=1;i<=m-j;i++)
                  
            {
                     mul(
            &t1,&Two_[m-j],a[nn][i]);
                     add(
            &t2,&d[i+1][i+j],&t1);
                     mul(
            &t3,&Two_[m-j],a[nn][i+j]);
                     add(
            &t4,&d[i][i+j-1],&t3);
                     
            if(high_max(&t2,&t4))
                       d[i][i
            +j]=t2;
                     
            else d[i][i+j]=t4;
                  }

                
            return d[1][m];
            }

            void end()
            {
                
            int i;
                high t1,t2,ans
            =zero;
                
            for(i=1;i<=n;i++)
                
            {
                   t1
            =ans;
                   t2
            =dp(i);
                   add(
            &ans,&t1,&t2);
                }

                print(
            &ans);
            }

            int main()
            {
                init();
                end();
            return 0;
            }

            posted on 2010-01-06 19:43 lee1r 閱讀(794) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:動態(tài)規(guī)劃
            99久久99久久精品免费看蜜桃| 久久久国产精品亚洲一区| 日产精品99久久久久久| 久久综合国产乱子伦精品免费| 亚洲欧洲久久av| 久久天堂AV综合合色蜜桃网| 女人香蕉久久**毛片精品| 精品国产综合区久久久久久| 青青草原综合久久大伊人| 国产亚洲精久久久久久无码77777| 久久久久久久久波多野高潮| 精品久久久久久99人妻| 亚洲欧美日韩久久精品| 久久午夜电影网| 久久精品无码一区二区三区| 俺来也俺去啦久久综合网| 国产成人精品久久一区二区三区av| 国产精品一区二区久久国产| 色综合久久无码五十路人妻| 久久综合伊人77777麻豆| 亚洲精品成人久久久| 国内精品久久久久久久久电影网 | 久久国产午夜精品一区二区三区| 日韩亚洲欧美久久久www综合网| 久久综合久久综合久久| 久久久WWW成人免费毛片| 亚洲色欲久久久综合网东京热| 国内精品久久久久久99| 精品国产综合区久久久久久| 色欲久久久天天天综合网| 一97日本道伊人久久综合影院| 久久99久久无码毛片一区二区| 国产精自产拍久久久久久蜜| 亚洲成色WWW久久网站| 一级a性色生活片久久无| 久久精品国产亚洲网站| 囯产精品久久久久久久久蜜桃| 欧美性大战久久久久久| 性高朝久久久久久久久久| 国产亚洲成人久久| 久久性精品|