题解 P1796 【汤姆斯的天堂梦_NOI导刊2010提高（05）】

Rainey · 2017-07-04 22:06:11 · 题解

一道比较简单的动态规划题，类似于数塔，有从上到下和从下到上两种解法，以i为等级，j为编号，L表示第i级编号j的星球到第i-1级编号k动态规划方程：f[i,j]=min{f[i-1,j]+L}

ps:题目有点小瑕疵，第二段应为“接下来的Ki行中第j行依次表示与等级为i，编号为j的星球相连的等级为i-1的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。"

#include<cstdio>
#include<climits>
using namespace std;
int f[200][200]={0};
int main()
{
    int n,a;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a);
        for(int j=1;j<=a;++j)
        {
            f[i][j]=INT_MAX-1000;//初始化，防止溢出
            int b,c;
            scanf("%d",&b);
            while(b!=0)
            {
                scanf("%d",&c);
                f[i][j]=f[i-1][b]+c<f[i][j]?f[i-1][b]+c:f[i][j];//DP
                scanf("%d",&b);
            }
        }
    }
    int min=INT_MAX;
    for(int i=1;i<=a;++i)//在最后一行中找最小值
        min=f[n][i]<min?f[n][i]:min;
    printf("%d",min);
    return 0;
}