POJ 1163 - The Triangle


问题描述

无。

解题思路

POJ3176 的解释。

不骗人,确实是一模一样的代码

AC 源码

//Memory Time 
//232K    0MS 

#include<iostream>
using namespace std;

int max(int a,int b)
{
    return a>b?a:b;
}

int main(int i,int j)
{
    int n;
    while(cin>>n)
    {
        int **way=new int*[n+1];   //动态申请二维数组的第一维,每个元素都是一个一维数组的指针

        /*Input & Initial*/

        for(i=0;i<=n;i++)
        {
            way[i]=new int[i+2]; //动态申请二维数组的第二维,每一行的空间
            for(j=0;j<=i+1;j++)
                way[i][j]=0;   //不能用memset初始化

            if(i!=0)
                for(j=1;j<=i;j++)
                    cin>>way[i][j];
        }

        /*Dp*/

        int max_weight=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=i;j++)
            {
                way[i][j] += max(way[i-1][j-1],way[i-1][j]);

                if(i==n && max_weight<way[i][j])
                    max_weight=way[i][j];
            }

        cout<<max_weight<<endl;

        delete[] way;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 3414 - Pots POJ 3414 - Pots
POJ 3414 - Pots Time: 1000MS Memory: 65536K 难度: 初级 分类: BFS 问题描述给出了两个瓶子的容量A,B, 以及一个目标水量C, 对A、B可以有如下操作: FILL(i): fill t
2011-02-17
下一篇 
POJ 2195 - Going Home POJ 2195 - Going Home
POJ 2195 - Going Home Time: 1000MS Memory: 65536K 难度: 中级 分类: 费用流 问题描述给定一个 N*M 的地图,地图上有若干个man和house,且man与house的数量一致。man
2011-02-15
  目录