P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述

汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球,有时需要向驾驶员支付一定金额的费用,有时却又可以得到一定的金钱。

汤姆斯预先知道了从0等级星球去N等级星球所有的航线和需要支付(或者可以得到)的金钱,他想寻找一条价格最低(甚至获得金钱最多)的航线。

输入输出格式

输入格式:

第一行一个正整数N(N≤100),接下来的数据可分为N个段落每段的第一行一个整数Ki(Ki≤100),表示等级为i的星球有Ki个。

接下来的Ki中第Tij行依次表示与等级为i,编号为i的星球相连的等级为i-l的星球的编号和此航线需要的费用(正数表示支出,负数表示收益,费用的绝对值不超过1000)。

每行以0结束,每行的航线数≤100。

输出格式:

输出所需(或所得)费用。正数表示支出,负数表示收益。

输入输出样例

输入样例#1:

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0

输出样例#1:

-1

说明

对于100%的数据N≤100 Ki≤100。

样例解释:

用t数组表示上一层的状态,用d数组表示本层的状态

转移方程d[i]=min(d[i],t[k]+m)

然后再把t数组替换为d数组

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9')
11     {c=getchar();if(c=='-')flag=1;}
12     while(c>='0'&&c<='9')
13     {x=x*10+(c-48);c=getchar();}
14     flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[10001];
18 int dp[10001][31];
19 int l,d[110],t[110]; 
20 int main()
21 {
22     int i,j,k;
23     read(n);
24     for (i=1;i<=n;i++)
25     {
26         read(k);
27         for (j=1;j<=k;j++)
28         {
29             d[j]=0x7ffff;        //将d[j]初始化 
30             read(l);
31             while (l!=0)
32             {
33                 read(m);
34                 if (d[j]>t[l]+m) d[j]=t[l]+m;
35                 read(l);
36             }
37         }
38         for (j=1;j<=k;j++)
39             t[j]=d[j];
40     }
41     int ans=1000000;
42     for (i=1;i<=k;i++){
43         if (ans>d[i]) ans=d[i];
44     }
45     printf("%d",ans);
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1272
来自专栏C语言及其他语言

初学C语言的学习计划

背景:很多同学在学习C语言的过程中,常常会遇到这样的问题,即“教材看完了,知识点也懂,但写不出来程序”,这段时间,我们通过长期与有多年C语言研究经验的教授、教师...

3674
来自专栏ACM算法日常

神、上帝以及老天爷(递推) - HDU 248

HDU 2006'10 ACM contest的颁奖晚会隆重开始了!为了活跃气氛,组织者举行了一个别开生面、奖品丰厚的抽奖活动,这个活动的具体要求是这样的: ...

1712
来自专栏JavaEdge

设计模式实战 - 抽象工厂模式导读定义适用场景优点缺点产品等级结构与产品族实践 coding

工厂方法模式人是造出来了,可都是清一色的类型,缺少关爱、仇恨、喜怒哀乐等情绪,人类的生命太平淡了,忘记给人类定义性别了,那怎么办? 从头开始建立所有的事物也是...

1601
来自专栏ACM算法日常

POJ2318 TOYS 判断点与直线位置关系 【计算几何】

Calculate the number of toys that land in each bin of a partitioned toy box.

1103
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

1.2K13
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机...

4736
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

4514
来自专栏web前端教室

重学javascript 红皮高程(5)

JS这项技术,细节到位了,就会一通百通。经常在网上看到说学一个框架,最有效的办法是去看它的源码。但我经常看不懂,为什么呢?因为我基础不好,不明白源码中的一些写法...

2085
来自专栏专知

【专知-关关的刷题日记18】Leetcode 35. Search Insert Position

题目 Given a sorted array and a target value, return the index if the target is fo...

3779

扫码关注云+社区

领取腾讯云代金券