&豪
豪->blog

隨筆 - 87 文章 - 279 trackbacks - 0

2006年2月

>

日

一

二

三

四

五

六

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

潛心看書研究！

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

HOJ
POJ
TOJ
URAL
UVA
ZOJ

My friends

搜索

積分與排名

積分 - 220588
排名 - 118

閱讀排行榜

評論排行榜

終于做出了一題IOI了，有點(diǎn)心得。

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

Sample Output

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。

這道題目，過得好辛苦，從開始的遞歸，到遞推加回溯，到窮舉，到窮舉加剪枝，結(jié)果就從TLE->TLE->TLE->WA. 一直用著要保留路徑的方法，所以怎么也做不出來，后來換了個思維角度，保存每一步的結(jié)果，動態(tài)規(guī)劃，終于就AC了。做了這題，另我復(fù)習(xí)了好幾種方法，也對DP有了深得認(rèn)識，可以說這是搞競賽的好題目，經(jīng)典，推薦??！

posted on 2006-02-21 13:09 豪閱讀(1626) 評論(6) 編輯收藏引用所屬分類: 算法&ACM

FeedBack:

# re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-02-21 20:58 豪

又忘記 delete []num 了！~~ 回復(fù) 更多評論

# re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-02-25 09:29 imlazy

加油。回復(fù) 更多評論

# re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-03-11 11:01 空明流轉(zhuǎn)

很好啊，再接再厲！
我的動態(tài)規(guī)劃一直學(xué)的不好。。。回復(fù) 更多評論

# re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-03-12 11:09 豪

感謝空明流轉(zhuǎn) 的支持!
我已經(jīng)領(lǐng)略到acm的恐怖了,但是我不會輕易放棄的:) 回復(fù) 更多評論

# re: 終于做出了一題IOI了，有點(diǎn)心得。 2006-08-12 21:15 Optimistic

加油！回復(fù) 更多評論

# re: 終于做出了一題IOI了，有點(diǎn)心得。 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;
}
亂寫的，感覺遞歸邏輯更加清晰:-) 回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 用stl打spfa短了1k代碼，慢了200ms 三次樣條插值龍貝格積分2457jlu 三分法求函數(shù)極值buaa1024 為了大作業(yè)報(bào)告好寫點(diǎn)，重寫了RBTree 擴(kuò)展的歐拉函數(shù) pku1091 連分?jǐn)?shù)學(xué)習(xí)筆記中國剩余定理(同余方程組)小結(jié) 解模線性方程小結(jié) 好久沒寫了.

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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