天啊。。。好多事。。。

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)就过了,都是编译器惹的祸...