青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219411
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

The Triangle
Time Limit:1000MS  Memory Limit:10000K

Description

7

3 8
8 1 0
2 7 4 4
4 5 2 6 5

(Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.

Output
Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output

30

Source
IOI 1994

#include<iostream>
using namespace std;

int main()
{
    
int n,digital_num;
    
int result[100][100];
    
int *num;
    
int max = 0;
    
int i,j;
    cin
>>n;
    digital_num 
= n;
    num 
= new int[digital_num];

    
for (i = 0; i<n; i++)
    
{
        
for (j = 0; j<=i; j++)
        
{
            cin
>>num[j];
            
if (i==0)
                result[i][j] 
= num[j];
            
if (i>0)
            
{
                
if (j==0)
                    result[i][j] 
= result[i-1][j]+num[j];
                
if (j==i)
                    result[i][j] 
= result[i-1][j-1]+num[j];
                
if (j>0&&j<i)
                
{
                   
if (result[i-1][j]>result[i-1][j-1])
                       result[i][j] 
= result[i-1][j]+num[j];
                   
else
                       result[i][j] 
= result[i-1][j-1]+num[j];
                }

            }

        }

    }

    
    
for (i = 0; i<n; i++)
        
if (result[n-1][i]>max)
            max 
= result[n-1][i];

    cout
<<max<<endl;
    
return 0;
}
上面是通過的原程序。140k,15MS。


這道題目,過得好辛苦,從開始的遞歸,到遞推加回溯,到窮舉,到窮舉加剪枝,結果就從TLE->TLE->TLE->WA.  一直用著要保留路徑的方法,所以怎么也做不出來,后來換了個思維角度,保存每一步的結果,動態規劃,終于就AC了。做了這題,另我復習了好幾種方法,也對DP有了深得認識,可以說這是搞競賽的好題目,經典,推薦!!
posted on 2006-02-21 13:09 閱讀(1623) 評論(6)  編輯 收藏 引用 所屬分類: 算法&ACM

FeedBack:
# re: 終于做出了一題IOI了,有點心得。 2006-02-21 20:58 
又忘記 delete []num 了!~~  回復  更多評論
  
# re: 終于做出了一題IOI了,有點心得。 2006-02-25 09:29 imlazy
加油。  回復  更多評論
  
# re: 終于做出了一題IOI了,有點心得。 2006-03-11 11:01 空明流轉
很好啊,再接再厲!
我的動態規劃一直學的不好。。。  回復  更多評論
  
# re: 終于做出了一題IOI了,有點心得。 2006-03-12 11:09 
感謝 空明流轉 的支持!
我已經領略到acm的恐怖了,但是我不會輕易放棄的:)  回復  更多評論
  
# re: 終于做出了一題IOI了,有點心得。 2006-08-12 21:15 Optimistic
加油!  回復  更多評論
  
# re: 終于做出了一題IOI了,有點心得。 2007-05-03 00:27 App
inline int calpos(int row,int col)
{

return row*(row-1)/2+col;
}
int tmem[5051]={-1,7,3,8,8,1,0,2,7,4,4,4,5,2,6,5};
int bestroute[5051]={-1};
int height=5;

int highestroute(int row,int col)
{
if (row>height)
{
return 0;
}
int pos=calpos(row,col);

if (bestroute[pos]>0)
{
return bestroute[pos];
}
int nr[]={1,0,1,1};
int max=0;
int i;
for (i=0;i<4;i+=2)
{
int tmp=highestroute(row+nr[i],col+nr[i+1]);
if (tmp>max)
{
max=tmp;
}
}
max+=tmem[pos];
bestroute[pos]=max;
return max;
}
亂寫的,感覺遞歸邏輯更加清晰:-)  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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久久综合婷婷| 亚洲国产日韩精品| 亚洲欧美影音先锋| 亚洲色图在线视频| 国产欧美一区二区三区在线老狼 | 久久aⅴ国产紧身牛仔裤| 亚洲自拍偷拍视频| 在线观看欧美成人| 亚洲黄网站黄| 国产精品v欧美精品v日韩| 欧美亚洲免费在线| 久久中文欧美| 亚洲欧美另类国产| 久久国产66| 日韩亚洲精品电影| 欧美一级淫片aaaaaaa视频| 亚洲国产高潮在线观看| 国产精品99久久久久久久久久久久 | 久久久久久久综合日本| 蜜臀久久99精品久久久久久9 | 国产欧美日韩综合一区在线播放| 久久全国免费视频| 欧美日本视频在线| 美日韩丰满少妇在线观看| 欧美日本中文字幕| 免费观看一区| 国产精品一区二区三区久久久| 欧美高清在线一区二区| 国产精品丝袜xxxxxxx| 亚洲高清在线| 精品盗摄一区二区三区| 亚洲一区二区三区激情| 亚洲精品一区中文| 欧美在线视频一区| 午夜精品国产精品大乳美女| 欧美高清你懂得| 久久综合伊人77777| 国产精品成人一区二区艾草| 亚洲成人在线网站| 激情综合久久| 欧美一区二区三区四区在线观看| 一区二区三区国产盗摄| 美女国产精品| 美日韩在线观看| 国产区亚洲区欧美区| 在线视频日本亚洲性| 日韩视频一区二区三区| 久久亚洲一区二区三区四区| 久久久久国产精品www| 国产精品久久久久久久久久免费看| 亚洲国产欧美另类丝袜| 在线成人免费视频| 久久久青草青青国产亚洲免观| 欧美淫片网站| 国产伦精品一区二区三| 亚洲男人的天堂在线观看| 亚洲欧美精品| 国产精品你懂的在线| 亚洲香蕉成视频在线观看| 亚洲私人影院| 国产精品黄视频| 一区二区欧美激情| 亚洲在线电影| 国产片一区二区| 欧美一区二区三区免费在线看| 久久gogo国模裸体人体| 国产精品最新自拍| 久久成人亚洲| 欧美电影打屁股sp| 亚洲精品社区| 欧美午夜精品久久久久久孕妇| 一区二区三区视频在线播放| 亚洲欧美一区二区三区久久| 国产毛片一区二区| 久久久99精品免费观看不卡| 欧美成人小视频| 9人人澡人人爽人人精品| 国产精品h在线观看| 午夜精品亚洲一区二区三区嫩草| 久久激情五月婷婷| 亚洲第一福利视频| 欧美日本在线播放| 午夜精品久久久久久久久| 免费不卡视频| 亚洲图色在线| 韩日在线一区| 欧美日韩成人在线视频| 亚洲女人天堂成人av在线| 另类酷文…触手系列精品集v1小说| 亚洲国产一成人久久精品| 国产精品v欧美精品∨日韩| 久久高清国产| 一本久久a久久精品亚洲| 久久精品国产综合| 日韩视频三区| 国产三级欧美三级日产三级99| 蜜臀a∨国产成人精品| 制服诱惑一区二区| 欧美成va人片在线观看| 亚洲欧美一级二级三级| 91久久国产综合久久蜜月精品| 国产精品九九久久久久久久| 久久亚洲欧洲| 亚洲女ⅴideoshd黑人| 亚洲国产一区二区a毛片| 性欧美videos另类喷潮| 亚洲精品人人| 精品动漫3d一区二区三区| 欧美三级午夜理伦三级中文幕| 久久久久久亚洲精品不卡4k岛国| 夜夜嗨av一区二区三区四区| 你懂的国产精品| 久久av一区二区三区漫画| 夜夜爽夜夜爽精品视频| 亚洲二区视频| 国内外成人免费激情在线视频| 欧美日韩国产三级| 欧美xxx在线观看| 久久国产精品99久久久久久老狼 | 久久久国产午夜精品| 一区二区三区视频观看| 亚洲欧洲在线免费| 在线免费观看视频一区| 国产亚洲精品bt天堂精选| 国产精品日韩在线播放| 欧美系列电影免费观看| 欧美日韩精品免费观看| 欧美激情综合五月色丁香| 久久青草福利网站| 久久精品一本| 久久精品国产v日韩v亚洲| 午夜精品福利一区二区蜜股av| 一二三四社区欧美黄| 亚洲精品一区二区在线观看| 亚洲黄色av一区| 亚洲国产精品传媒在线观看| 欧美大成色www永久网站婷| 久久综合伊人77777蜜臀| 久久免费视频观看| 久久久蜜桃一区二区人| 久久久久久久波多野高潮日日| 久久成人精品无人区| 欧美亚洲系列| 久久久久国产精品人| 久久久欧美一区二区| 久久亚洲精品一区二区| 久久亚洲综合色| 欧美承认网站| 亚洲精品乱码久久久久久日本蜜臀| 亚洲国产精彩中文乱码av在线播放| 欧美国内亚洲| 亚洲乱码久久| 亚洲视频国产视频| 欧美中文字幕不卡| 久久伊人精品天天| 欧美黄色一区二区| 欧美午夜电影一区| 国产午夜精品美女毛片视频| 红桃视频国产精品| 亚洲精选在线观看| 亚洲一区二区在线观看视频| 久久国产精品黑丝| 欧美激情一区二区三区在线视频观看| 欧美黄色免费网站| 一区二区三区高清在线| 久久超碰97中文字幕| 欧美顶级少妇做爰| 国产精品高潮视频| 亚洲春色另类小说| 亚洲欧美激情一区二区| 久久综合一区二区三区| 99re热这里只有精品免费视频| 亚洲免费视频观看| 欧美gay视频激情| 国产精品一区二区三区乱码 | 国产精品成人国产乱一区| 国产日韩视频一区二区三区| 亚洲国产精品www| 亚洲综合色在线| 免费在线亚洲欧美| 亚洲视屏在线播放| 久久综合九色综合欧美就去吻| 欧美午夜不卡影院在线观看完整版免费| 国产亚洲精品激情久久| 99在线热播精品免费| 久久视频在线看| 亚洲视频一区二区| 欧美激情欧美激情在线五月| 国产性做久久久久久| 99视频精品全国免费| 美女国产一区| 亚洲欧美日韩另类精品一区二区三区| 欧美/亚洲一区| 永久免费视频成人| 欧美一区二区三区视频在线| 亚洲欧洲日韩综合二区| 久久频这里精品99香蕉| 国产日韩在线视频| 亚洲欧美日韩精品在线| 亚洲精选在线|