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

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 流牛ζ木馬 閱讀(1486) 評論(1)  編輯 收藏 引用

評論

# re: ACM PKU 1163 The Triangle 簡單的動態規劃就像是APM小于等于100的WAR3玩家 2007-11-08 00:20 流牛ζ木馬

哦對了,注意兩點.
一是數組定義一定要放在全局的位置,局部變量名字最好不要重復, 不知道為什么,否則有時通不過,很詭異..但是在自己的機器上測試卻不存在這點  回復  更多評論   

刷新評論列表

只有注冊用戶登錄后才能發表評論。

網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理

Powered by:
C++博客
Copyright © 流牛ζ木馬

導航

• C++博客
• 首頁
• 新隨筆
• 聯系
• 聚合
• 管理

統計

• 隨筆 - 63
• 文章 - 0
• 評論 - 154
• 引用 - 0

公告

常用鏈接

• 我的隨筆
• 我的評論
• 我參與的隨筆

留言簿(6)

• 給我留言
• 查看公開留言
• 查看私人留言

隨筆檔案

• 2008年10月 (1)
• 2008年2月 (1)
• 2007年11月 (23)
• 2007年9月 (38)

相冊

• 撒旦

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜