ACM PKU 1163 The Triangle 简单的动态规划就像是APM小于等于100的WAR3玩家

http://acm.pku.edu.cn/JudgeOnline/problem?id=1163
简单的动态规划就像是APM小于等于100的WAR3玩家,可以变着戏法来随便虐待.
递推式的动归、记忆化搜索，或者稍微优化一下的搜索……

呵呵，

a[i][j]是i排第j个数
f[i][j]是到达a[i][j]时可以得到的最大总和.
显然只能从a[i-1][j-1]和a[i-1][j]两条路来到a[i][j]
故状态转移方程为 f[i][j]=max{a[i-1][j],a[i-1][j-1]}+a[i][j]
注意边界条件即可
#include "stdio.h"
int a[100][100];
int f[100][100];


int max(int x,int y)
{
    if(x>y)return x;
    else return y;
}


void main()
{

    int result;
    int i,j;
    int m;

    scanf("%d",&m);
    for(i=1;i<=m;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&a[i][j]);    

    f[0][0]=0; f[0][1]=0;
    for(i=1;i<=m;i++)
    {
        f[i][0]=0;f[i][i+1]=0;
        for(j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j]; 
    }


    result=f[m][1];
    for(i=1;i<=m;i++)
        if(f[m][i]>result)result=f[m][i];
    printf("%d\n",result);


}

posted on 2007-11-08 00:19 流牛ζ木马 阅读(1398) 评论(1)  编辑 收藏 引用

评论

# re: ACM PKU 1163 The Triangle 简单的动态规划就像是APM小于等于100的WAR3玩家 2007-11-08 00:20 流牛ζ木马

哦对了,注意两点.
一是数组定义一定要放在全局的位置,局部变量名字最好不要重复, 不知道为什么,否则有时通不过,很诡异..但是在自己的机器上测试却不存在这点  回复  更多评论   


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


<2007年11月>
日一二三四五六
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜