传送门：  【POJ】3169 Layout、【HDU】3592 World Exhibition 题目分析：我会说我只是凭直觉写的吗。。。。。。。 如果有B-A>=C形式的，则建边(B,A,-C)。 如果有B-A<=C形式的，则建边(A,B,C)。 对所有的点X，建边(X,X-1,0)。 最后跑一遍最短路。如果存在负环输出-1，如果点N不可达输出-2，否则输出点N的值（最短路径长

【题目链接】：click here~~ 【题意】： 题意：给定n头牛的聪明指数S和幸福指数F，如果存在S的和TS>=0与F的和TF>=0同时成立时， 输出TS与TF的和的最大值sum，否则，输出0。 【思路】：      转化问题，求s和为某个固定值时候最大的f和值，然后遍历这些所有的s和以及对应的f和值，求出总和总和最大的那个。      那么这样就是一个0-1背包问题，可以把s值理解

一.题目链接： HDU-3592 二.题目大意： 有 n 个人排队，第 i 个人的位置 ≤ 第 i + 1 个人的位置. 有 x 种关系，a b c 表示 a 与 b 之间的距离最大为 c. 有 y 种关系，a b c 表示 a 与 b 之间的距离最小为 c. 求 1 到 n 的最小距离. 若无解，输出 -1. 若可无限大，输出 -2. 否则输出最小距离. 三.分析： 模板题

感觉像是之前做过的题的加强版😅 考虑容斥哪些区间不合法。直接处理比较困难，考虑将所有区间按右端点排序，并将端点离散化（将右端点 + 1 +1 +1，转化为左闭右开区间），设 d p i , j , k dp_{i,j,k} dpi,j,k​表示只考虑前 i i i个区间，以及 [ 1 , j ) [1,j) [1,j)这段前缀，上一个选择的区间类型是 k ∈ [ 0 , 1 ] k\in [0

感觉像是之前做过的题的加强版😅 考虑容斥哪些区间不合法。直接处理比较困难，考虑将所有区间按右端点排序，并将端点离散化（将右端点 + 1 +1 +1，转化为左闭右开区间），设 d p i , j , k dp_{i,j,k} dpi,j,k​表示只考虑前 i i i个区间，以及 [ 1 , j ) [1,j) [1,j)这段前缀，上一个选择的区间类型是 k ∈ [ 0 , 1 ] k\in [0

2184 Cow Exhibition 0－1背包问题变形，选定一个值作状态后，另一值可被标识。如果有更多信息需记录（信息量－1）的数组应该可以的。http://acm.pku.edu.cn/JudgeOnline/problem?id=1717 Dominos这道题也是一道类似的题目，还可以用搜索来做。把有利的值统统加入，同时记下可能使不符合的元素，做一次排除，找到正确的最优值。  0－1背包

A. Sonya and Hotels 题目网址 点击打开链接 time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Sonya decided that having her own hotel b

题目链接 Description “Fat and docile, big and dumb, they look so stupid, they aren’t much fun…” -Cows with Guns by Dana Lyons The cows want to prove to the public that they are both smart and fun. In or