[综合] 洛谷OJ - P1843 - 奶牛晒衣服（二分答案）

题目描述 熊大妈请你帮助完成这个重任。洗完衣服后，你就要弄干衣服。衣服在自然条件下用1的时间可以晒干A点湿度。抠门的熊大妈买了1台烘衣机。使用烘衣机可以让你用1的时间使1件衣服除了自然晒干A点湿度外，还可以烘干B点湿度，但在1的时间内只能对1件衣服使用。N件衣服因为种种原因而不一样湿，现在告诉你...

[综合] 洛谷OJ - P2757 - 导弹的召唤(数据加强)（二分优化LIS）

题目描述 易琢然今天玩使命召唤，被敌军用空对地导弹轰炸，很不爽；众所周知，易琢然很不老实，他开了外挂；外挂第一次可以打掉任意高度的导弹，之后每一次都不能打掉大于上一次高度的导弹；但易琢然水平太差，敌军最多有300000颗导弹，导弹只能按顺序打，因为外挂有BUG,而且是超音速导弹，只有一秒导弹就到...

[综合] 第八届蓝桥杯【省赛试题9】分巧克力

题目描述 儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有N块巧克力，其中第i块是HixWi的方格组成的长方形。为了公平起见，小明需要从这N块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：1.形状是正方形，边长是整数2.大小相同例如一块6x5的巧克力...

[综合] 洛谷OJ - P1892 - 团伙（并查集）

题目描述 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。 输入 输入文件g...

[综合] 洛谷OJ - P2024 - 食物链（并查集）

题目描述 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是“1XY”，表示X和Y是同类。第二种...

[综合] 洛谷OJ - P1525 - 关押罪犯（并查集）

题目描述 S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同...

[综合] 洛谷OJ - P1060 - 开心的金明（01背包）

题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了...

[综合] 洛谷OJ - P1064 - 金明的预算方案（并查集+附加条件）

题目描述 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是...

[综合] NYOJ - 746 - 整数划分（四）（区间DP）

题目描述 暑假来了，hrdv又要留学校在参加ACM集训了，集训的生活非常Happy（ps：你懂得），可是他最近遇到了一个难题，让他百思不得其解，他非常郁闷。。亲爱的你能帮帮他吗？ 问题是我们经常见到的整数划分，给出两个整数n,m,要求在n中加入m-1个乘号，将n分成m段，求出这m段的最大乘积 ...

[综合] NYOJ - 15 - 括号匹配（二）（区间DP）

题目描述 给你一个字符串，里面只包含"(",")","[","]"四种符号， 请问你需要至少添加多少个括号才能使这些括号匹配起来。 如： []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N，表示测试数据组数(N<...

[综合] 洛谷OJ - P1880 - 石子合并（区间DP）

题目描述 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分. 输入 数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第...

[综合] NYOJ - 737 - 石子合并（一）（区间DP）

题目描述 有N堆石子排成一排，每堆石子有一定的数量。 现要将N堆石子并成为一堆。 合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。 求出总的代价最小值。 输入 有多组测试数据，输入到文件结束。每组测试数据第一行有一个整数n...

[综合] 洛谷OJ - P1091 - 合唱队形（LIS）

题目描述 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形： 设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1&...

[综合] 洛谷OJ - P1108 - 低价购买（LIS+方案数）

题目描述 “低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时...

[综合] 洛谷OJ - P1025 - 数的划分（递归取球问题）

题目描述 将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。 例如：n=7，k=3，下面三种分法被认为是相同的。 1，1，5; 1，5，1; 5，1，1; 问有多少种不同的分法。 输入 n，k(6<n<=200，2<=k<=6) 输...

[综合] 洛谷OJ - P1057 - 传球游戏（记忆化搜索）

题目描述 上体育课的时候，小蛮的老师经常带着同学们一起做游戏。 这次，老师带着同学们一起做传球游戏。 游戏规则是这样的： n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师在此吹哨子时，传球停...

[综合] 洛谷OJ - P1135 - 奇怪的电梯（DFS+回溯+减枝）

题目描述 呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例...

[综合] 洛谷OJ - P1182 - 数列分段Section II（二分答案）

题目描述 对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。 关于最大值最小：例如一数列42451要分成3段将其如下分段：[42][45][1]第一段和为6，第2段和为9，第3段和为1，和最大值为9。 将其如下分段：[4][24...

[综合] 洛谷OJ - P1316 - 丢瓶盖（二分答案）

题目描述 陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？ 输入 第一行，两个整数，A,B。（B<=A<=100000） 第二行，A个整数，分别为这A个瓶盖...

[综合] LeetCode 119. Pascal's Triangle II

Pascal'sTriangleII 题目描述: Givenanindexk,returnthekthrowofthePascal'striangle. Forexample,givenk=3,Return[1,3,3,1]. Note:Couldyouoptimizeyouralgorithmt...