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

隨筆 - 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>
              亚洲国产精品va在线看黑人 | 欧美一区综合| 亚洲国产另类久久久精品极度| 欧美丝袜第一区| 久久午夜av| 性xx色xx综合久久久xx| 在线视频日韩| 欧美激情精品久久久久久变态| 欧美亚洲在线视频| 午夜精品美女久久久久av福利| 亚洲专区一区二区三区| 日韩亚洲国产欧美| 一区二区三区日韩欧美| 欧美影院成人| 老司机午夜免费精品视频| 在线看片欧美| 国产视频亚洲精品| 依依成人综合视频| 亚洲黄色有码视频| 亚洲成色www8888| 亚洲人成毛片在线播放| 久久尤物视频| 麻豆成人在线| 激情欧美国产欧美| 在线一区二区三区做爰视频网站| 最新日韩av| 欧美日韩精品在线观看| 久久婷婷人人澡人人喊人人爽| 久久视频在线看| 99国产精品99久久久久久| 午夜精品亚洲一区二区三区嫩草| 欧美日韩国产123区| 亚洲男女自偷自拍| 亚洲国产一区二区三区a毛片| 久久在线91| 亚洲国产日日夜夜| 亚洲欧美另类久久久精品2019| 国产欧美日本| 欧美激情bt| 久久精品国产2020观看福利| 国产精品毛片在线| 欧美精品www在线观看| 欧美午夜视频网站| 尤物视频一区二区| 亚洲午夜激情网站| 另类尿喷潮videofree| 欧美在线视频一区二区| 久久精品一区二区三区不卡| 国语自产精品视频在线看抢先版结局 | 午夜精品短视频| 久久久久九九九| 亚洲每日在线| 久久精品成人一区二区三区蜜臀 | 看片网站欧美日韩| 亚洲美女精品久久| 亚洲亚洲精品三区日韩精品在线视频 | 欧美 日韩 国产 一区| 亚洲精品乱码久久久久久久久| 亚洲男人av电影| 国产精品一区二区视频| 久久久久久久综合色一本| 欧美一级久久久| 亚洲电影观看| 久久精品成人一区二区三区| 久久午夜激情| 国产精品xxxxx| 18成人免费观看视频| 欧美一区二区在线播放| 在线免费观看日本欧美| 欧美日韩一区国产| 久久九九久久九九| 欧美一区二区三区成人| 久久久www成人免费无遮挡大片| 亚洲激情在线观看| 美女国产一区| 精品不卡在线| 黄色成人在线网站| 国产精品video| 欧美99久久| 亚洲黄色毛片| 蜜桃av综合| 久久福利视频导航| 国产精品a久久久久久| 久久精品视频va| 久久精品免费电影| 日韩视频中午一区| 亚洲精品一区二区在线| 亚洲精品欧美激情| 国产一区二区高清不卡| 亚洲一区综合| 日韩一级免费| 在线欧美视频| 亚洲欧美中文日韩在线| 亚洲激情电影中文字幕| 99re在线精品| 久久精品中文字幕一区| 9色精品在线| 免费亚洲电影在线| 亚洲午夜日本在线观看| 免费不卡亚洲欧美| 久久一区中文字幕| 亚洲欧美日韩一区二区在线| 欧美乱大交xxxxx| 欧美一区二区三区婷婷月色| 欧美成人精品影院| 亚洲欧美日韩一区二区三区在线观看 | 久久午夜色播影院免费高清| 美女视频黄免费的久久| 国产精品毛片一区二区三区| 欧美色网一区二区| 欧美日韩精品免费观看| 精品1区2区3区4区| 99综合电影在线视频| 欧美成人a∨高清免费观看| 久久久精品国产免费观看同学| 久久国产精品第一页| 国产精品一区2区| 欧美影院精品一区| 欧美一区二区三区视频在线| 国产一区导航| 欧美成人r级一区二区三区| 免费影视亚洲| 亚洲欧美日韩综合| 欧美韩日视频| 欧美四级在线观看| 久久精品免费播放| 亚洲少妇中出一区| 国产精品久久一区主播| 日韩视频在线一区二区| 99国产一区| 亚洲第一精品福利| 亚洲神马久久| 亚洲精品久久久久| 91久久综合| 在线播放不卡| 久久精品视频网| 亚洲欧美日韩区| 免费观看成人www动漫视频| 久久久999精品视频| 国产精品毛片a∨一区二区三区| 亚洲少妇诱惑| 欧美激情一区二区三区高清视频| 在线看无码的免费网站| 亚洲欧美在线网| 亚洲区免费影片| 亚洲欧美在线网| 欧美久久成人| 欧美国产极速在线| 国产欧美视频在线观看| 久久综合久久久久88| 欧美日韩国产美| 久久精品国产第一区二区三区| 噜噜噜躁狠狠躁狠狠精品视频 | 国产精品女主播在线观看| 久久精品国产一区二区三区免费看 | 亚洲作爱视频| 裸体一区二区三区| 欧美综合第一页| 欧美亚洲视频| 欧美sm视频| 99视频在线精品国自产拍免费观看| 亚洲综合好骚| 午夜伦欧美伦电影理论片| 国产婷婷成人久久av免费高清| 久久亚洲风情| 亚洲欧美日本日韩| 亚洲经典三级| 欧美aⅴ99久久黑人专区| 亚洲午夜小视频| 日韩视频一区二区三区| 亚洲人人精品| 久久精品水蜜桃av综合天堂| 久久亚洲精品一区二区| 免费在线看成人av| 午夜精品久久久久久久白皮肤 | 国产啪精品视频| 国产精品爽黄69| 99亚洲伊人久久精品影院红桃| 亚洲一二三区精品| 欧美va亚洲va国产综合| 久久看片网站| 午夜精品久久久久久久蜜桃app| 国模精品娜娜一二三区| 国产精品入口尤物| 欧美激情亚洲自拍| 欧美精品一区在线播放| 性欧美暴力猛交另类hd| 亚洲香蕉伊综合在人在线视看| 日韩视频免费观看| 一本久久a久久免费精品不卡| 久久久久久国产精品一区| 久久亚洲二区| 欧美伊人影院| 久久字幕精品一区| 欧美怡红院视频| 欧美日本在线观看| 欧美日韩一区二区在线观看视频| 欧美激情第六页| 欧美国产日韩免费| 国产精品观看|