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

隨筆 - 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>
              久久狠狠婷婷| 亚洲性视频网站| 亚洲黄色av一区| 欧美日韩国产二区| 午夜视频一区| 亚洲黄一区二区三区| 亚洲精品在线视频观看| 国产精品伦一区| 久久婷婷国产麻豆91天堂| 99视频在线观看一区三区| 久久精品亚洲热| 亚洲经典自拍| 影音先锋欧美精品| 国产日韩精品视频一区二区三区| 久久久久久久久久久久久9999| 日韩亚洲欧美一区二区三区| 欧美xart系列高清| 久久精品91久久久久久再现| 亚洲午夜精品一区二区| 亚洲精选在线| 亚洲欧洲日本一区二区三区| 韩日欧美一区| 在线精品亚洲一区二区| 国际精品欧美精品| 国产亚洲欧美日韩一区二区| 国产欧美精品在线| 国产视频亚洲| 国产亚洲欧美aaaa| 国产欧美日韩一区二区三区在线| 欧美日韩精品不卡| 国产伦精品一区二区三区高清| 欧美天堂亚洲电影院在线播放| 欧美三级中文字幕在线观看| 欧美日韩网址| 国产亚洲一区二区在线观看| 黄色av成人| 日韩亚洲一区二区| 欧美在线视频网站| 欧美激情精品久久久久| 亚洲毛片在线看| 久久精品一区二区三区中文字幕| 久久久青草婷婷精品综合日韩 | 欧美国产在线观看| 欧美精品日日鲁夜夜添| 欧美日韩在线免费| 国产精品日本精品| 海角社区69精品视频| 亚洲精品视频在线观看网站| 一区二区日韩| 欧美一区二区三区视频免费播放| 先锋影音久久| 亚洲第一福利视频| 亚洲午夜一区二区| 开心色5月久久精品| 欧美网站在线观看| 91久久黄色| 久久精品91久久久久久再现| 欧美成人免费大片| 午夜精品成人在线| 欧美日韩国产高清| 久久人人爽人人爽| 午夜精品影院| 欧美日韩一视频区二区| 亚洲国产裸拍裸体视频在线观看乱了中文| 亚洲伦理在线观看| 毛片av中文字幕一区二区| 亚洲午夜影视影院在线观看| 蜜桃av一区二区| 国内精品一区二区三区| 欧美伊人精品成人久久综合97| 亚洲黄页视频免费观看| 免费试看一区| 在线看欧美日韩| 亚洲婷婷在线| 在线视频亚洲欧美| 欧美性大战久久久久久久| 在线亚洲精品| 在线国产精品一区| 欧美岛国激情| 欧美日本一道本| 一本色道久久综合亚洲精品婷婷| 亚洲精品日韩激情在线电影| 欧美午夜一区二区| 亚洲视频一区| 午夜精品视频网站| 亚洲美女色禁图| 欧美网站在线| 亚洲免费小视频| 香蕉久久夜色精品国产| 激情综合在线| 欧美成人xxx| 欧美日韩成人在线视频| 欧美一区视频| 欧美精品九九| 久久精品亚洲一区二区| 欧美黄色日本| 久久成人精品电影| 久久露脸国产精品| 午夜精品免费视频| 欧美国产大片| 欧美亚洲在线播放| 欧美日韩一区在线视频| 久久精品视频导航| 国产精品色婷婷| 欧美激情第10页| 国产最新精品精品你懂的| 欧美激情第五页| 狠狠色狠狠色综合| 午夜精品久久久| 亚洲女女女同性video| 欧美日本免费| 亚洲乱码日产精品bd| 日韩视频在线观看免费| 久久久精品国产一区二区三区| 性久久久久久久久久久久| 噜噜噜91成人网| 免费h精品视频在线播放| 久久久久久久尹人综合网亚洲 | 久久精品水蜜桃av综合天堂| 国产精品自在在线| 亚洲自拍电影| 久久精品国产999大香线蕉| 国产乱肥老妇国产一区二| 亚洲精品视频在线| 亚洲欧美在线aaa| 国产嫩草影院久久久久| 欧美一区二区三区四区在线| 久久精品视频在线播放| 欧美一区二区三区四区视频| 亚洲精品一区在线观看| 欧美日韩亚洲成人| 模特精品在线| 久久久久久久网站| 老司机成人网| 亚洲视频大全| 红桃视频国产一区| 欧美乱妇高清无乱码| 一区二区av在线| 久久久中精品2020中文| 日韩视频一区二区在线观看| 国产精品免费一区二区三区在线观看 | 亚洲精品视频免费观看| 伊人精品在线| 国产精品丝袜白浆摸在线| 欧美激情在线狂野欧美精品| 午夜欧美精品| 午夜在线精品偷拍| 亚洲美女在线国产| 亚洲国产日韩一区| 欧美激情在线观看| 另类综合日韩欧美亚洲| 欧美一区二区在线播放| 久久不射2019中文字幕| 亚洲一区二区三区色| 1769国产精品| 亚洲区国产区| 亚洲国产精品热久久| 一区二区欧美激情| 久久久一区二区三区| 久久超碰97中文字幕| 亚洲欧洲日韩综合二区| 国产精品视频一| 亚洲少妇在线| 亚洲激情女人| 免费国产自线拍一欧美视频| 国产专区精品视频| 亚洲视频中文| 欧美激情一区二区三区在线视频| 亚洲视频高清| 欧美日韩天堂| 亚洲精品一区二区在线观看| 久久久免费精品| 一本色道久久综合亚洲二区三区| 久久久久国色av免费观看性色| 欧美日韩1234| 99re这里只有精品6| 欧美va亚洲va日韩∨a综合色| 亚洲一级在线观看| 欧美亚州一区二区三区 | 日韩午夜免费| 久久久99久久精品女同性| 日韩小视频在线观看专区| 久热精品在线| 一区二区三区在线视频观看| 久久av二区| 久久一区中文字幕| 亚洲精品一区二区三区不| 欧美丰满高潮xxxx喷水动漫| 久久久免费精品视频| 亚洲二区精品| 欧美激情精品| 欧美日本一区二区三区| 中文精品视频| 亚洲一区二区三区精品视频| 国产精品一区毛片| 久久久精品五月天| 欧美激情在线播放| 久久福利电影| 欧美激情综合五月色丁香小说| 午夜精品久久久|