随笔 - 87  文章 - 279  trackbacks - 0
<2006年2月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
2627281234
567891011

潜心看书研究！

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211853
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

终于做出了一题IOI了，有点心得。

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 豪 阅读(1581) 评论(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;
}
乱写的，感觉递归逻辑更加清晰:-)  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 豪 Powered by: 博客园 模板提供：沪江博客