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

隨筆 - 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在线观看h| 一区二区三区www| 一区二区三区视频免费在线观看| 欧美视频日韩视频在线观看| 亚洲综合日韩| 一区二区三区国产在线观看| 9久草视频在线视频精品| 欧美专区在线观看一区| 亚洲国产黄色| 一本到12不卡视频在线dvd| 国产精品乱码| 欧美大片一区二区三区| 欧美日韩中文字幕在线| 久久视频国产精品免费视频在线| 久久香蕉国产线看观看网| 99国产精品视频免费观看| 亚洲一区视频在线| 91久久精品美女| 亚洲视频免费看| 在线国产日韩| 亚洲视频免费在线观看| 亚洲高清激情| 亚洲欧美在线高清| 99国产精品国产精品久久| 亚洲在线第一页| 亚洲六月丁香色婷婷综合久久| 在线综合亚洲欧美在线视频| 在线精品亚洲| 午夜一区二区三区不卡视频| 亚洲美女视频在线免费观看| 欧美亚洲在线观看| 亚洲一区二区三区在线视频| 噜噜噜在线观看免费视频日韩| 欧美有码视频| 欧美视频在线观看免费| 欧美高清在线视频| 国产在线播放一区二区三区| 夜夜嗨av一区二区三区网页 | 亚洲精品在线看| 老色鬼精品视频在线观看播放| 亚洲在线1234| 欧美日韩亚洲视频| 亚洲电影免费在线| 国产在线观看91精品一区| 99视频超级精品| 一本久道久久综合婷婷鲸鱼 | 亚洲欧洲日本mm| 在线欧美电影| 久久久噜噜噜久久中文字幕色伊伊| 亚洲欧美不卡| 国产精品久久久久9999高清| 亚洲免费精彩视频| 日韩视频―中文字幕| 免费视频一区| 欧美国产欧美综合| 亚洲精品1区2区| 久久不射网站| 亚洲激情网站| 蜜桃av噜噜一区二区三区| 久久香蕉国产线看观看网| 国产精自产拍久久久久久蜜| 亚洲专区在线视频| 亚洲欧美成人一区二区在线电影 | 一区二区电影免费在线观看| 99精品国产福利在线观看免费 | 亚洲视频在线观看三级| 亚洲一区三区电影在线观看| 国产精品vvv| 一区二区三区日韩精品视频| 亚洲综合二区| 国产一区二区高清不卡| 久久久999精品免费| 欧美福利一区| 日韩一级在线| 国产精品日本| 久久久久免费观看| 欧美成人精品一区二区| 亚洲经典三级| 欧美va天堂| 一区二区激情视频| 久久国产综合精品| 亚洲国产综合在线看不卡| 欧美精品免费视频| 亚洲欧美在线播放| 欧美搞黄网站| 午夜精品福利在线观看| 黄色成人av网| 欧美日韩亚洲一区二区| 欧美亚洲三区| 亚洲欧洲在线看| 欧美一区二区三区在线观看| 在线观看免费视频综合| 欧美中文字幕视频| 亚洲黄色免费| 久久国产乱子精品免费女| 亚洲精品乱码久久久久| 国产精品久久久爽爽爽麻豆色哟哟| 久久av二区| 一区二区三区四区国产精品| 久久夜色精品国产欧美乱极品| 夜夜嗨av色综合久久久综合网| 国产精品一区视频| 欧美国产乱视频| 小嫩嫩精品导航| 欧美激情成人在线视频| 亚洲欧美国产毛片在线| 最新国产成人在线观看| 国产啪精品视频| 欧美电影在线免费观看网站| 小辣椒精品导航| 一本色道久久加勒比88综合| 久久综合狠狠综合久久综合88| 亚洲自拍偷拍福利| 亚洲伦伦在线| 黄色亚洲免费| 国产精品腿扒开做爽爽爽挤奶网站| 免费日本视频一区| 久久久国产一区二区三区| 亚洲综合社区| 一本色道久久综合亚洲91| 欧美激情精品久久久久久黑人| 久久久高清一区二区三区| 亚洲制服av| 在线亚洲一区二区| 91久久线看在观草草青青| 国产精品专区h在线观看| 欧美色123| 欧美视频在线一区二区三区| 欧美美女喷水视频| 欧美国产日韩xxxxx| 久久综合九色综合久99| 久久青草久久| 久久久久九九九九| 久久福利一区| 久久九九精品99国产精品| 欧美伊人精品成人久久综合97| 午夜电影亚洲| 亚洲欧美日韩精品| 亚洲欧美日韩另类| 亚洲欧美视频| 欧美一区日韩一区| 欧美中日韩免费视频| 久久久久久久波多野高潮日日| 久久不射电影网| 久久艳片www.17c.com| 久久综合久久综合九色| 欧美成在线观看| 欧美日韩久久久久久| 国产精品免费一区二区三区在线观看 | 欧美精品三区| 欧美精品在线观看一区二区| 欧美日本精品在线| 欧美视频免费在线观看| 国产精品午夜在线观看| 国产一区二区三区自拍| 亚洲第一在线| 亚洲精品国偷自产在线99热| 99国产精品久久久久久久| 亚洲午夜电影在线观看| 亚洲欧美国产视频| 欧美中文字幕在线播放| 久久综合九九| 亚洲国产欧美一区二区三区久久| 亚洲人成欧美中文字幕| 这里只有精品电影| 久久爱另类一区二区小说| 欧美a级一区| 国产精品嫩草99av在线| 狠狠色伊人亚洲综合成人| 亚洲人成亚洲人成在线观看| 亚洲综合日韩在线| 美女精品网站| 在线一区二区三区做爰视频网站 | 欧美一区二区视频观看视频| 噜噜噜躁狠狠躁狠狠精品视频 | 亚洲一区在线免费| 久久久天天操| 国产精品国产福利国产秒拍 | 欧美视频中文字幕在线| 国产日韩欧美另类| 亚洲国产裸拍裸体视频在线观看乱了中文| 91久久极品少妇xxxxⅹ软件| 亚洲欧美国产另类| 欧美承认网站| 亚洲尤物在线| 欧美激情一区二区三区在线| 国产精品一区二区在线观看不卡| 亚洲国产精品va在线观看黑人 | 一区二区欧美视频| 久久婷婷av| 99re6这里只有精品| 久久精品国产清自在天天线| 欧美午夜在线一二页| 1024欧美极品| 久久久久中文| 亚洲自拍16p| 欧美日韩一区二区三区在线看| 国产一区二区高清|