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

ACM PKU 1163 The Triangle 簡(jiǎn)單的動(dòng)態(tài)規(guī)劃就像是APM小于等于100的WAR3玩家

http://acm.pku.edu.cn/JudgeOnline/problem?id=1163
簡(jiǎn)單的動(dòng)態(tài)規(guī)劃就像是APM小于等于100的WAR3玩家,可以變著戲法來隨便虐待.
遞推式的動(dòng)歸、記憶化搜索，或者稍微優(yōu)化一下的搜索……

呵呵，

a[i][j]是i排第j個(gè)數(shù)
f[i][j]是到達(dá)a[i][j]時(shí)可以得到的最大總和.
顯然只能從a[i-1][j-1]和a[i-1][j]兩條路來到a[i][j]
故狀態(tài)轉(zhuǎn)移方程為 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) 評(píng)論(1)  編輯 收藏 引用

評(píng)論

# re: ACM PKU 1163 The Triangle 簡(jiǎn)單的動(dòng)態(tài)規(guī)劃就像是APM小于等于100的WAR3玩家 2007-11-08 00:20 流牛ζ木馬

哦對(duì)了,注意兩點(diǎn).
一是數(shù)組定義一定要放在全局的位置,局部變量名字最好不要重復(fù), 不知道為什么,否則有時(shí)通不過,很詭異..但是在自己的機(jī)器上測(cè)試卻不存在這點(diǎn)  回復(fù)  更多評(píng)論   

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。

網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理

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

導(dǎo)航

• C++博客
• 首頁(yè)
• 新隨筆
• 聯(lián)系
• 聚合
• 管理

統(tǒng)計(jì)

• 隨筆 - 63
• 文章 - 0
• 評(píng)論 - 154
• 引用 - 0

公告

常用鏈接

• 我的隨筆
• 我的評(píng)論
• 我參與的隨筆

留言簿(6)

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

隨筆檔案

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

相冊(cè)

• 撒旦

搜索

最新隨筆

最新評(píng)論

閱讀排行榜

評(píng)論排行榜