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

            M.J的blog

            algorithm,ACM-ICPC
            隨筆 - 39, 文章 - 11, 評論 - 20, 引用 - 0
            數據加載中……

            TOJ 2812. Travel

            簡單的DP,很好想。但是我第一次又給做成了貪心···相當無奈,不知道什么時候才能分清貪心和DP的區別。

            初始化很重要,讓我WA了N次。

            dp[i][j]表示第  i天在 city j 所能得到的最大income。

            所以有轉移方程:

            dp[i][j] = max{ dp[i-1][j]-pay[j][j]+income[i-1][j] ,dp[i-1][k]-pay[k][j]+income[i-1][j]};

            其中1<k<=n  (dp[1][i]單獨初始化)

            Code:

             1 #include<iostream>
             2 #define MAX 120
             3 using namespace std;
             4 int m,n,dp[MAX][MAX];
             5 int pay[MAX][MAX],income[MAX][MAX];
             6 int main()
             7 {
             8     int i,j,k,temp,mm;
             9     while(cin>>n>>m){
            10         if(m==0&&n==0break;
            11         mm=-1000000;
            12         for(i=1;i<=n;i++)
            13              for(j=1;j<=n;j++)
            14                    cin>>pay[i][j];
            15         for(i=1;i<=m;i++)
            16              for(j=1;j<=n;j++)
            17                    cin>>income[i][j];
            18         dp[0][1]=0;
            19         for(i=1;i<=n;i++)
            20              dp[1][i]=income[1][i]-pay[1][i];
            21         for(i=2;i<=m;i++)
            22              for(j=1;j<=n;j++){
            23                    temp=dp[i][j]=dp[i-1][j]-pay[j][j]+income[i][j];
            24                    for(k=1;k<=n;k++)
            25                           if(temp<dp[i-1][k]-pay[k][j]+income[i][j]){
            26                                 dp[i][j]=dp[i-1][k]-pay[k][j]+income[i][j];
            27                                 temp=dp[i][j];
            28                           }
            29              }
            30             
            31         for(i=1;i<=n;i++)
            32              if(dp[m][i]>mm)
            33                  mm=dp[m][i];
            34         cout<<mm<<endl;
            35     }
            36 
            37 }

            posted on 2010-04-24 08:52 M.J 閱讀(91) 評論(0)  編輯 收藏 引用

            国内精品伊人久久久久影院对白| 一本久久a久久精品亚洲| 99久久成人18免费网站| 久久综合中文字幕| 久久伊人精品青青草原高清| 久久av免费天堂小草播放| 中文字幕久久波多野结衣av| 久久久久久亚洲AV无码专区| 国内精品久久久久久久久| 麻豆av久久av盛宴av| 99国产欧美久久久精品蜜芽 | 99久久国产亚洲综合精品| 99久久国产综合精品女同图片| 久久亚洲国产精品一区二区| 国产精品久久久久a影院| 久久噜噜电影你懂的| 亚洲αv久久久噜噜噜噜噜| 品成人欧美大片久久国产欧美| 国内精品久久久久久久久电影网| 青青草原综合久久| 久久亚洲精品成人AV| 天天综合久久一二三区| 精品久久久久久国产| 久久夜色精品国产噜噜亚洲a| 久久精品国产精品青草app| 亚洲AV无码1区2区久久 | 成人精品一区二区久久| 亚洲国产另类久久久精品黑人| 婷婷久久综合| 久久香蕉国产线看观看猫咪?v| 国产精品美女久久久久AV福利| 国产精品久久一区二区三区| 久久Av无码精品人妻系列| 久久九九久精品国产免费直播| 久久影院久久香蕉国产线看观看| 91久久精品电影| 91麻精品国产91久久久久| 亚洲精品高清国产一久久| 久久精品无码一区二区三区| 日本福利片国产午夜久久| 久久综合综合久久97色|