• <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)  編輯 收藏 引用

            波多野结衣久久精品| 亚洲熟妇无码另类久久久| 亚洲av成人无码久久精品| 久久99国产精品尤物| 69SEX久久精品国产麻豆| 91精品久久久久久无码| 久久久久久亚洲精品不卡| 97精品伊人久久大香线蕉| 亚洲级αV无码毛片久久精品| 999久久久无码国产精品| 久久综合综合久久97色| 一极黄色视频久久网站| 97r久久精品国产99国产精| 久久九九免费高清视频| 一本久久a久久精品亚洲| 久久亚洲高清观看| 亚洲狠狠婷婷综合久久久久| 精品久久久久中文字幕一区| 一本色道久久99一综合| 99久久国产综合精品网成人影院| 2020久久精品亚洲热综合一本| 狠狠色婷婷综合天天久久丁香| 99久久国产亚洲综合精品| 一本色道久久88加勒比—综合| 国产A级毛片久久久精品毛片| 久久精品国产亚洲一区二区三区 | 九九久久精品无码专区| 久久99久国产麻精品66| 国产L精品国产亚洲区久久| 日韩人妻无码精品久久免费一| 亚洲国产日韩欧美综合久久| 品成人欧美大片久久国产欧美... 品成人欧美大片久久国产欧美 | 色综合久久无码中文字幕| 久久亚洲欧洲国产综合| 一本大道久久a久久精品综合| 国内精品久久久人妻中文字幕| 亚洲乱码中文字幕久久孕妇黑人| 久久久久综合国产欧美一区二区| 国产亚州精品女人久久久久久 | 久久中文字幕一区二区| 国产产无码乱码精品久久鸭|