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

隨筆 - 87  文章 - 279  trackbacks - 0
<2006年2月>
2930311234
567891011
12131415161718
19202122232425
2627281234
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最新网址| 亚洲精品黄网在线观看| 国产欧美一区二区三区国产幕精品 | 国产综合色产在线精品| 欧美xart系列高清| 国产精品久久久久久久久果冻传媒| 欧美一区二区视频免费观看| 狂野欧美激情性xxxx| 性欧美激情精品| 欧美精品亚洲| 亚洲福利视频二区| 韩国av一区二区三区四区| 一区二区日韩精品| 国产精品久久久久久久久久久久 | 久久精品免费观看| 在线视频免费在线观看一区二区| 亚洲欧美影音先锋| 亚洲女优在线| 久久久综合香蕉尹人综合网| 欧美日韩国产美| 亚洲人精品午夜| aaa亚洲精品一二三区| 欧美剧在线观看| 一区二区欧美精品| 欧美一区二区三区在| 国产精品日韩欧美| 久久av一区二区| 欧美国产激情二区三区| 91久久在线观看| 欧美日韩大片| 亚洲欧美国产毛片在线| 欧美一区成人| 亚洲激情影视| 国产精品theporn| 久久er精品视频| 久久天天躁夜夜躁狠狠躁2022| 激情视频亚洲| 欧美日韩在线电影| 久久亚洲综合| 亚洲午夜高清视频| 欧美第十八页| 久久久精品免费视频| 亚洲欧洲午夜| 激情综合色丁香一区二区| 欧美欧美全黄| 欧美成人亚洲| 欧美一区激情视频在线观看| 亚洲精品国产精品久久清纯直播 | 免费高清在线视频一区·| av成人免费观看| 91久久午夜| 黄色日韩在线| 狠狠色狠狠色综合人人| 国产精品国产三级国产 | 午夜性色一区二区三区免费视频| 国产主播在线一区| 国内精品伊人久久久久av影院| 欧美日韩亚洲视频| 欧美精品日本| 欧美日韩另类一区| 欧美日韩精品久久久| 欧美性色综合| 国产伦理精品不卡| 国产日韩欧美综合精品| 国产精品久久久久秋霞鲁丝 | 一区二区三区 在线观看视| 亚洲电影在线| 日韩手机在线导航| 亚洲一区二区伦理| 亚洲欧美日韩一区在线| 久久嫩草精品久久久久| 欧美顶级少妇做爰| 在线亚洲精品| 久久另类ts人妖一区二区| 欧美成人免费va影院高清| 欧美好骚综合网| 国产欧美一二三区| 最新亚洲电影| 久久成人资源| 99精品国产在热久久婷婷| 欧美一区二区三区视频免费| 蜜乳av另类精品一区二区| 欧美日韩精品免费看| 激情欧美丁香| 亚洲字幕一区二区| 欧美高清视频www夜色资源网| 中国女人久久久| 欧美激情精品久久久久| 国产精自产拍久久久久久| 亚洲激情电影在线| 麻豆九一精品爱看视频在线观看免费| 亚洲精品一区二区三区福利 | 亚洲成色777777女色窝| 欧美一区二区三区在线免费观看| 亚洲精品久久久久久久久久久久久| 亚洲欧美在线网| 国产区欧美区日韩区| 亚洲欧美大片| 欧美一区二区三区精品电影| 国产精品毛片高清在线完整版| 国产综合色产在线精品| 亚洲激情另类| 久久天堂av综合合色| 欧美在线精品一区| 伊大人香蕉综合8在线视| 欧美专区福利在线| 欧美在线网站| 亚洲人成网站在线播| 亚洲国产成人精品久久久国产成人一区| 欧美中文日韩| 亚洲高清视频在线| 艳女tv在线观看国产一区| 欧美日本一区| 美日韩丰满少妇在线观看| 久久综合中文| 欧美一区二区三区在线播放| 午夜精品视频在线观看| 一区在线影院| 亚洲图中文字幕| 亚洲欧洲另类国产综合| 亚洲一区二区三区三| 91久久精品国产91久久性色tv| 一本色道久久综合亚洲精品不卡| 国产一二三精品| 日韩一级成人av| 亚洲国产成人av| 欧美一区网站| 欧美在线视频一区二区| 欧美激情国产日韩| 欧美大片免费久久精品三p| 国产精品一区二区在线观看| 亚洲精品小视频| 亚洲老板91色精品久久| 麻豆91精品| 亚洲电影中文字幕| 亚洲久久在线| 欧美黄色小视频| 亚洲精品中文字| 亚洲午夜精品国产| 国产精品magnet| 亚洲欧美在线视频观看| 久久成人精品无人区| 国产欧美一区二区三区在线老狼| 一区二区欧美视频| 久久久久国产精品一区| 国内精品视频一区| 欧美国产精品| 亚洲免费视频在线观看| 久久一区二区三区四区| 亚洲电影观看| 国产精品女主播在线观看| 亚洲一区二区三区欧美| 久久亚洲风情| 亚洲一区一卡| 在线精品高清中文字幕| 欧美日本高清| 久久蜜桃精品| 午夜伦理片一区| 最新国产乱人伦偷精品免费网站| 永久免费精品影视网站| 久久精品综合| 亚洲午夜在线| 91久久一区二区| 狂野欧美一区| 久久精品国产第一区二区三区最新章节 | 日韩视频在线观看免费| 久久久久久久91| 亚洲免费在线视频一区 二区| 在线成人欧美| 一区二区三区在线观看视频| 欧美日韩黄视频| 欧美高清视频免费观看| 另类尿喷潮videofree| 欧美与黑人午夜性猛交久久久| 日韩视频专区| 一区二区三区视频在线观看 | 欧美国产日韩一区二区| 久久精品在线观看| 久久久五月天| 免费在线成人| 亚洲理伦在线| 一本色道久久综合亚洲二区三区| 亚洲人成网站影音先锋播放| 亚洲激情在线激情| 日韩一区二区精品视频| 中文在线资源观看网站视频免费不卡 | 一本综合精品| 久久精品一区二区三区四区| 久久久噜噜噜久久| 牛牛国产精品| 国产欧美精品日韩区二区麻豆天美|