hdu1224 Free DIY Tour--DP
二:分析理解
发布日期:2021-10-03 20:32:03
浏览次数:4
分类:技术文章
本文共 3468 字,大约阅读时间需要 11 分钟。
原题链接:
一:原题内容
Problem Description
Weiwei is a software engineer of ShiningSoft. He has just excellently fulfilled a software project with his fellow workers. His boss is so satisfied with their job that he decide to provide them a free tour around the world. It's a good chance to relax themselves. To most of them, it's the first time to go abroad so they decide to make a collective tour. The tour company shows them a new kind of tour circuit - DIY circuit. Each circuit contains some cities which can be selected by tourists themselves. According to the company's statistic, each city has its own interesting point. For instance, Paris has its interesting point of 90, New York has its interesting point of 70, ect. Not any two cities in the world have straight flight so the tour company provide a map to tell its tourists whether they can got a straight flight between any two cities on the map. In order to fly back, the company has made it impossible to make a circle-flight on the half way, using the cities on the map. That is, they marked each city on the map with one number, a city with higher number has no straight flight to a city with lower number. Note: Weiwei always starts from Hangzhou(in this problem, we assume Hangzhou is always the first city and also the last city, so we mark Hangzhou both 1 and N+1), and its interesting point is always 0. Now as the leader of the team, Weiwei wants to make a tour as interesting as possible. If you were Weiwei, how did you DIY it?
Input
The input will contain several cases. The first line is an integer T which suggests the number of cases. Then T cases follows. Each case will begin with an integer N(2 ≤ N ≤ 100) which is the number of cities on the map. Then N integers follows, representing the interesting point list of the cities. And then it is an integer M followed by M pairs of integers [Ai, Bi] (1 ≤ i ≤ M). Each pair of [Ai, Bi] indicates that a straight flight is available from City Ai to City Bi.
Output
For each case, your task is to output the maximal summation of interesting points Weiwei and his fellow workers can get through optimal DIYing and the optimal circuit. The format is as the sample. You may assume that there is only one optimal circuit. Output a blank line between two cases.
Sample Input
230 70 9041 21 32 43 430 90 7041 21 32 43 4
Sample Output
CASE 1#points : 90circuit : 1->3->1CASE 2#points : 90circuit : 1->2->1
设 dp[i] 为从城市 1 到城市 i 所能够获得的最大 interesting point
三:AC代码
#include#include #include using namespace std;int visit[110][110];int pre[110];int points[110];int dp[110];void Out(int p){ if (p == 1) { printf("1->"); return; } Out(pre[p]); printf("%d->", p);}int main(){ int T; int N; int M; int x, y; scanf("%d", &T); for (int cas = 1; cas <= T; cas++) { if (cas != 1) printf("\n"); memset(visit, 0, sizeof(visit));// memset(points, 0, sizeof(points));// memset(dp, 0, sizeof(dp));// scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d", &points[i]); scanf("%d", &M); for (int i = 0; i < M; i++) { scanf("%d %d", &x, &y); visit[x][y] = 1; } dp[N + 1] = 0;// for (int i = 1; i <= N + 1; i++) { for (int j = 0; j < i; j++) { if (visit[j][i]) { if (dp[i] < dp[j] + points[i]) { dp[i] = dp[j] + points[i]; pre[i] = j; } } } } printf("CASE %d#\n", cas); printf("points : %d\n", dp[N + 1]); printf("circuit : "); Out(pre[N + 1]); printf("1\n"); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50992071 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月06日 08时58分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
@Value注解不能注入static修饰的属性
2019-04-27
spring boot 2.x 接口返回时间类型不再自动序列化为timestamp
2019-04-27
Ubuntu Linux 创建root用户并且允许远程登录
2019-04-27
Linux shell 关于 2>&1 的含义
2019-04-27
Ubuntu Linux系统使用apt-get install安装的软件的相关位置
2019-04-27
nginx同一server配置多个前端工程location访问404问题
2019-04-27
前端嫌弃原生Swagger界面太low,于是我给她开通了超级VIP
2019-04-27
小白都能学会的Java注解与反射机制
2019-04-27
Java高并发测试框架JCStress
2019-04-27
阿里P8大神教我yaml语法,我终于不再只是使用字符串类型了
2019-04-27
Springboot 集成 i8n,两行代码实现国际化,你不想学吗?
2019-04-27
LeetCode 每日一题「判定字符是否唯一」
2019-04-27
Oracle中wm_concat的使用
2019-04-27
国庆第四天出行归来
2019-04-27
宝宝游乐园的优化思路(r6笔记第72天)
2019-04-27
UI5_INFO_FETCH_FROM_DB
2019-04-27
SAP CRM WebClient UI的配置存储数据库表
2019-04-27
SAP C4C Mashup port bindingF4帮助对话框里的数据源
2019-04-27
SAP C4C产品主数据OData服务的ETag处理
2019-04-27