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

隨筆 - 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>
              欧美jjzz| 久久久国产视频91| 欧美三级电影一区| 亚洲午夜一区二区三区| 亚洲视频一区二区免费在线观看| 国产精品亚洲综合| 久久av老司机精品网站导航| 久久久久久久久蜜桃| 最新亚洲激情| 一区二区日韩免费看| 国产一区二区久久久| 女同性一区二区三区人了人一| 欧美国产综合| 性色av一区二区三区红粉影视| 欧美在线观看视频一区二区三区 | 国产精品v欧美精品v日韩| 午夜视黄欧洲亚洲| 老司机免费视频一区二区| 中文欧美日韩| 久久精品首页| 亚洲婷婷在线| 久久久久久一区二区三区| 亚洲免费观看高清完整版在线观看熊 | 欧美久久成人| 欧美一区二区三区在线视频| 老司机久久99久久精品播放免费| 亚洲免费在线视频| 久久久青草婷婷精品综合日韩| 99精品国产热久久91蜜凸| 香蕉成人啪国产精品视频综合网| 亚洲欧洲日本专区| 欧美一区二区三区在线看| 日韩一级大片| 久久久亚洲欧洲日产国码αv| 亚洲香蕉伊综合在人在线视看| 久久久久在线观看| 香蕉久久国产| 欧美日韩在线不卡一区| 欧美激情 亚洲a∨综合| 激情综合网址| 亚洲欧美变态国产另类| 亚洲乱码久久| 美女脱光内衣内裤视频久久影院| 久久精品国产99| 国产精品三区www17con| 日韩视频永久免费观看| 91久久精品一区二区别| 久久久久久久网| 久久精品日产第一区二区三区| 欧美视频在线观看一区| 亚洲精品四区| 亚洲美女中文字幕| 久久综合九色综合欧美狠狠| 久久亚洲综合色| 国产视频综合在线| 亚洲欧美在线一区| 久久成人人人人精品欧| 国产精品日韩精品| 亚洲欧美日韩在线播放| 先锋影音久久久| 国产精品无码专区在线观看| 中文日韩在线| 性色一区二区三区| 国产色产综合产在线视频| 亚洲在线观看视频网站| 久久国产66| 国内外成人免费激情在线视频网站 | 日韩一级成人av| 欧美先锋影音| 翔田千里一区二区| 麻豆精品在线视频| 91久久精品国产91性色tv| 欧美aaa级| 日韩午夜av电影| 午夜在线视频观看日韩17c| 国产丝袜一区二区| 久久久噜噜噜| 一本大道久久精品懂色aⅴ| 亚洲欧美日韩爽爽影院| 国产亚洲在线观看| 欧美 日韩 国产在线| 亚洲精品午夜| 久久国产精品亚洲77777| 一区二区三区在线观看国产| 欧美va亚洲va日韩∨a综合色| 亚洲精品综合在线| 欧美中日韩免费视频| 在线成人www免费观看视频| 麻豆精品精华液| 亚洲伦理在线免费看| 午夜精品视频在线观看| 国产色产综合产在线视频| 久久亚洲私人国产精品va| 亚洲高清视频在线观看| 一区二区三区高清| 国产精品视频第一区| 久久久久88色偷偷免费| 欧美日韩在线另类| 蜜臀av性久久久久蜜臀aⅴ| 欧美激情视频在线播放 | 免费观看日韩| 久久激情网站| 国产精品一二一区| 久久综合九色综合久99| 99re热这里只有精品视频| 性色av一区二区三区| 亚洲激情国产| 国产精品久久久久久久久动漫| 欧美专区18| 亚洲天堂av在线免费| 快射av在线播放一区| 一级日韩一区在线观看| 国产揄拍国内精品对白| 欧美精品久久久久久久久老牛影院 | 欧美.www| 日韩一区二区精品视频| 国产一区久久久| 欧美日韩在线播放一区| 欧美一级午夜免费电影| 美国成人直播| 久久国产视频网站| 99在线观看免费视频精品观看| 国产日本欧洲亚洲| 欧美激情欧美狂野欧美精品| 久久成人精品视频| 欧美插天视频在线播放| 久久久久一区二区三区| 亚洲永久免费av| 亚洲激情成人在线| 国产综合色在线| 欧美日韩视频免费播放| 欧美韩国日本综合| 久久深夜福利| 久久久久国产一区二区三区四区| 欧美岛国激情| 久久国产精品网站| 亚洲一区二区三区中文字幕在线| 亚洲欧洲精品一区二区| 激情久久五月| 激情欧美一区| 韩国精品久久久999| 国产在线日韩| 国产欧美va欧美va香蕉在| 欧美岛国在线观看| 欧美日本免费一区二区三区| 农夫在线精品视频免费观看| 久久嫩草精品久久久精品| 欧美一区二区高清在线观看| 日韩视频不卡中文| 亚洲一级在线观看| 亚洲视屏一区| 亚洲在线成人精品| 亚洲一区在线观看免费观看电影高清| 亚洲激情国产| 99热免费精品在线观看| 日韩视频中文字幕| 日韩亚洲视频在线| 一区二区三区视频在线观看| 亚洲精品在线视频| 亚洲亚洲精品在线观看| 亚洲欧美精品suv| 欧美在线高清视频| 久久午夜色播影院免费高清| 久久精品电影| 另类图片综合电影| 欧美大香线蕉线伊人久久国产精品| 蜜桃久久av一区| 欧美日本簧片| 国产一区二区三区直播精品电影| 一区二区三区在线视频免费观看 | 欧美成年视频| 国产精品劲爆视频| 国产日韩欧美综合一区| 在线日韩中文| 午夜日韩电影| 老司机免费视频久久| 亚洲高清视频中文字幕| 这里只有视频精品| 欧美一区二区播放| 欧美激情精品久久久久久免费印度| 欧美日韩亚洲91| 国产一区免费视频| 亚洲精品一区二区三区婷婷月| 在线一区亚洲| 欧美3dxxxxhd| 亚洲视频综合| 久久青草久久| 国产精品美女主播| 欧美激情中文字幕一区二区 | 夜夜爽夜夜爽精品视频| 性感少妇一区| 欧美aa在线视频| 欧美成人精品| 欧美一级二级三级蜜桃| 久久综合九色综合欧美就去吻| 国产精品久久久久久久久免费樱桃 | 午夜国产精品视频免费体验区| 模特精品在线| 国产日韩精品电影| 亚洲免费高清视频|