某山寨

z4zr的待调教小窝

POJ1163 Triangle DP入门题目

Tag:C/C++ dp poj acm

POJ1163 Triangle DP入门题目

POJ1163
记得第一次遇到这个题目的时候 当时束手无策啊。。
那个时候 脑袋笨笨的 只想着从上向下计算但是结果还不对。。。
后来想到了从下向上的加和,每次都保存最大的结果,思路出来了就
没经过正规的培训。。。 后来知道属于 DP的多段图

思路: 从最下面的开始 取自己下面的两个点中最大的点加到自己的位置上 使每一层的解为最优的解(最小状态最优化) map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
#include<stdio.h>
#include<string.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    int map[105][105];
    int n,i,j;
    while(scanf("%d",&n)!=EOF){
        memset(map,0,sizeof(map));
        for(i=0;i<n;i++){
            for(j=0;j<=i;j++){
                scanf("%d",&amp;map[i][j]);
            }
        }
        for(i=n-2;i>=0;i--){
            for(j=0;j<=i;j++){
                map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
                //printf("%3d",map[i][j]);
            }
            //puts("");
        }
        printf("%d\n",map[0][0]);
    }
    return 0;
}

Warning: file_get_contents(http://api.hitokoto.us/rand): failed to open stream: Connection timed out in /data/htdocs/z4zr.host.smartgslb.com/usr/themes/Wcat/functions.php on line 87

文章二维码