天啊。。。好多事。。。

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有了深得認識，可以說這是搞競賽的好題目，經典，推薦！！ 忽然間，宿舍的寧靜一去不復返，忽然間，想起了和chgsh吃飯時候說的一句話：
        他說：灰色的天空，編織著灰色的夢；
        我說：灰色的夢中，有一個你和我。

天啊，多么肉麻！

有夢，總比無夢好。每個人的成功，或多或少，都是他們當初的夢吧！雖然天空是灰色，夢是灰色，但是當你做到能喜歡那種灰色的時候，那離你的夢想就不遠了。

又想起一句套話，高三作文題目用過：讓我痛并快樂著吧。而且最終是快樂的，我相信！！ 一，別以為在學生會你能得到你曾經想要的。工作的熱情很可能因為你所看到的所經歷的一些事而改變，但是也不必懼怕。你有大一一年來適應或者承受，并做出是繼續堅持還是退出的決定。 

二，大學可能有真實的愛情，但是記住只是可能。很多時候他們是因為別人都談戀愛而羨慕或者別的原因而在一起。所以，不必為任何分手而受太大的傷，記住，太大的傷，真愛，還是值得追求的。 

三，如果你的家庭一般的話，那么記得你在大學有很多意外用錢的地方。比如二專業或者將來的各種班，為了你的家人和你自己的前途，永遠別亂花錢。記住，永遠。 

四，朋友，你大學的朋友很可能就是你將來事業的一部分。他們會幫助你。但是你也應該讓自己有幫助他們的實力，所以，你要努力，你和你的朋友會一起在將來打造一個可能很輝煌的事業。很好聽是嗎？但是記住，你們都要努力。 

五，很多事情當你再回憶時會發現其實沒什么。所以，不管你當時多么生氣憤怒或者別的，都告訴自己不必這樣，你會發現其實真的不必。 

六，學習，永遠別忘記她。不管別人怎么說大學是個提高綜合能力的地方云云，如果你學習失敗了，你就什么也不是——不排除意外，但你考慮好了嗎？你會是那個意外嗎？？ 

七，別說臟話，你應該知道習慣的力量。找工作或者和別人接觸時，你隨便的一個字或者幾個字會讓你在別人心中的形象大打折扣。 

八，好好利用在公共場合說話的機會，展示或者鍛煉，都可以。 

九，別為你自己和別人下定論，無比重要。你所看到聽到的可能只是一面，為這個失去可能的朋友，很不值。 

十，如果你發現很久了你一直是一個人去食堂吃飯或者去上自習，別在意，大學里一個人是正常的，你覺得孤獨？你的朋友是怕你覺得你沒有自由的空間，所以別以為你沒有朋友。 

十一，很多事情別人通知你了，要說謝謝，沒有通知你，不要責怪，因為那些事你其實應該自己弄清楚。 

十二,"我請你吃飯"之類的話不要亂說,因為所有人都會當真,不管你自己怎么想,大學里請人吃飯是很平常的事,幾乎連請一個自己不怎么認識的人吃飯都很正常. 

十三,尊嚴是最重要的,但是在大學里，要懂得利用這個空間鍛煉自己,要讓自己的尊嚴有足夠大的承受力,要知道,社會是一個最喜歡打碎人的尊嚴的地方,除了你自己,沒人會為你保留它. 

十四,大學是亞社會.對,所以,當你上了高年級后,要讓自己有大人的形象,大一的孩子看到你,你要能讓他們感覺到你是他們的學長.你很成熟. 

十五,你有足夠的理由佩服每天早起的人,不信的話,你去做.做到后會發現有很多人佩服你呢. 

十六,經常給家里打個電話,即使他們說不想你. 

十七,你可以有喝醉的時候,我們可以接受,但是你要明白和真正的朋友一醉才能讓傷心事方休,否則,你只會是別人的談資和笑柄. 

十八,如果你四年內很少去圖書館的話,你就等于自己浪費了一大筆一大筆財富.所以,長去那里,隨意翻翻,都有收獲. 

十九,不論男人還是女人,如果在大學里還把容貌當作重要的東西而過分重視的話,可能不會吃虧,但是早晚會吃虧.可能,很可能. 

二十,面試時很多老總會問你----如果你能見到老總的話-----你會做什么??也許你現在其實就可以記得這個問題,這樣可能以后會好好回答-----尤其對文科學生來說. 
二十一，新學期如果你接新生的話，當被問到學校怎么樣之類的問題時，你要記住你不但是這個學校的一分子，你更要給你學弟學妹帶來信心，你走過大一，你應該知道那時候對學長的信任多深。 

二十二，別總抱怨不公平，你的不公平對別人是公平的，辨證法——高三時學的，忘記了？ 

二十三，別迷戀網絡游戲。千萬別。 

二十四，"我愛你"。別對很多人說這句話，在大學里，我的意思是，希望你只對一個人說，這是尊重你愛的人，更是尊重你自己的感情 

二十五，大學，因為你呆的地方是大學，所以你有空間承受失敗和打擊，因此，你應該......真的應該，找找......自信和自傲的區別，可以用一輩子的。 

二十六，如果你的個性讓很多人對你敬而遠之，那么你的個性是失敗的，個性的成功在于能吸引，而不是能排斥。 

二是七，如果把上課不睡覺當做一種鍛煉并且你做到了，那么，你很強，而且記住，其實你應該是這樣的，老師再差，也比學生強，因為他們是老師。 

二十八，學生會的主席之類的干部，如果你尊重他們，告訴你自己那是因為他們是你的學長而不是因為他們是你的上級，事實上，大家都只是學生而已，只是學生。 

二十九，瘋狂英語的話：別怕丟人，如果你實在不行就別怕丟人，行的話，建議你們-去追求丟人，那是一種成功的嘗試，至于為此笑話你的人，你可以把他們從你將來人生對手的名單中排除了，所以你也不要笑話那些上臺丟人的人。 

三十,從絕望中尋找希望,人生終將輝煌. 

三十一,如果你不抽煙的話,你的精力將比抽煙的時候好的多,這是絕對的. 

三十二,你的確要學的有心計,但是記住,永遠記住,在社會上要勝利的唯一的方法永遠只是一個,那就是實力,永遠不用懷疑. 

三十三,面對不公平的東西,不要抱怨,你的不公平可能恰恰是別人的公平.所以, 你不如去努力的奮斗,爭取你自己最合適的公平. 

三十四,人生百態,不要對新的看不慣的東西生氣,無所謂的,比如說戀人同居問題,和我們很多人無關的. 

三十五,別總請人吃飯,別總讓別人請你吃飯______朋友除外!!!!! 

三十六,在大學里就開始訓練自己的冷靜力,這是一種能力的,有大事時,能安靜并能快速想出辦法的人,很厲害. 

三十七,大學的競爭范圍是所有的大學生,所以,你知道是否可以放松學習的. 

三十八,大了,成熟了,穩重了 ,但是這和激情不矛盾,一種對工作和學習的沖擊力及持久力會讓你有特殊的魅力和個人實力 

三十九，記著 在所謂的學生會里即便你就是主席 如果你的四級沒過沒有畢業證 的話 白搭 沒單位想要你這樣的人 單位需要的是工作的人 而不是當官的人 更何況現在的就是主席 學到的是喝酒 抽煙 相互的 吹捧 

四十 永遠不要嘲笑你的教師無知或者單調，因為有一天當你發現你用瞌睡來嘲弄教師實際上很愚蠢時，你在社會上已經碰了很多釘子了。 

四十一 不要幻想自己成為招聘會上的寵兒，當你明白百分之七十的初中生都可以上大學時，你應該明白人們不會去崇拜一個群體的大多數的。 

四十二 英語一定要學好，但英語絕對不會是你生活的全部保障，所以多學點東西可能有時會救命的 

四十三，你可以看不慣一些東西，但是你應該學會接受——如果你沒法改變那一切的話。 

四十四，對陌生人，或者把對方當做一張白紙，或者把對方當你的朋友，總之別當做敵人，即使你聽到再多的關于他（她）的不好的傳聞。 

四十五，愛你的人，不管你接不接受，你都應該感謝對方，這是對你們的尊重。 

四十六，在晚上，聽聽收音機也是種快樂和幸福。 

四十七： 每個星期一定要抽時間出來鍛煉身體的。好處多多。 

四十八，如果周圍有人嫉妒你，那么你可以把他從你的競爭者之列排除了，嫉妒人之人，難以成大事。 

四十九，別去爭論，可以回憶一下，你會發現，人不可能贏得爭論，可以說，爭論所提級的話題都是不值得去爭論的。 

五十，成功的方法多種多樣 ，別不接受你看不慣的方法。 原題: A Simple Task
Given a positive integer n and the odd integer o and the nonnegative
integer p such that n = o2^p.


Example

For n = 24, o = 3 and p = 3.


Task

Write a program which for each data set:

reads a positive integer n,

computes the odd integer o and the nonnegative integer p such that n = o2^p,

writes the result.


Input

The first line of the input contains exactly one positive integer d
equal to the number of data sets, 1 <= d <= 10. The data sets follow.

Each data set consists of exactly one line containing exactly one
integer n, 1 <= n <= 10^6.


Output


Line i, 1 <= i <= d, corresponds to the i-th input and should contain two
integers o and p separated by a single space such that n = o2^p.


Sample Input

1
24


Sample Output

3 3

  上面是我提交的程序
在zju提交編譯錯誤一次  因為標準c++   pow函數為 pow(double,<type>)第一個參數必須為double,但是我再shantou 上用pow(int,int)就過了,都是編譯器惹的禍...