sticks专题

【UVA】10003-Cutting Sticks（动态规划、矩阵链乘）

一道动态规划题，不过似乎可以用回溯水过去，回溯的话效率很烂的。 13988658 10003 Cutting Sticks Accepted C++ 1.882 2014-08-04 09:26:49 AC代码： #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include

poj1011 (Sticks)

自己加了些注释和排序方法转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1311647833 解题思路： DFS+剪枝 POJ2362的强化版，重点在于剪枝令InitLen为所求的最短原始棒长，maxlen为给定的棒子堆中最长的棒子，sumlen为这堆棒子的长度之和，那么InitLen必定在范围[maxlen，

CF 258A. Game With Sticks

http://codeforces.com/contest/451/problem/A 很有意思的题目，大水 A. Game With Sticks time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Uva | Cutting Sticks

原题 You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery,Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of wor

Sticks ---- 深度优先搜索+剪枝优化

这是我第一道接触剪枝算法的题目，剪枝的用处就是为了优化深度优先搜索的时间复杂的，使其代码跑的更快。 Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 118677 Accepted: 27381 Description George took sticks of the same length and cut

[LightOJ 1342] Aladdin and the Magical Sticks （期望的线性性质+几何分布+邮票收集问题）

LightOJ - 1342 有 N根棍子，每根棍子都有一个权值其中有若干根可识别的，若干根不可识别的抽到了可识别的棍子，就不放回，抽到了不可识别的，就要放回问所有棍子都至少被抽过一次后的期望权值和根据期望的线性性， E(CX)=CE(X) E(CX) = CE(X) 所以可以对每根棍子求一下它被抽到的期望次数，再乘以它的权值对于不可识别的棍子，由于它被抽到的概率

[Codeforces 451A] Game With Sticks （博弈）

Codeforces - 451A N根横向木棍，M根纵向木棍组成了一个网格图每次可以选择一个交点，去掉所有通过这个交点的木棍两个人交替进行这个游戏，问最后谁能胜利每次选择的一个交点，必然去掉了一根横向木棍和纵向木棍所以每次 N和 M都减一当其中有一个为 0的时候，就是先手必败态所以只和 N、M中较小的那个的奇偶性有关 #pragma comment(link

uvalive 2322 Wooden Sticks(贪心）

题目连接：2322 Wooden Sticks 题目大意：给出要求切的n个小木棍，每个小木棍有长度和重量，因为当要切的长度和重量分别大于前面一个的长度和重量的时候可以不用调整大木棍直接切割，否则要进行调整。现在要求求出一个序列，使得调整的次数最少，输出调整的次数。解题思路：将n个小木棍先按照长度和重量的大小排序，然后按照顺序将小木棍分堆，可入堆的要求是长度和重量大于当

poj 2513 Colored Sticks

题目链接：点击打开链接 Description You are given a bunch(群) of wooden sticks. Each endpoint(端点) of each stick is colored with some color. Is it possible to align(结盟) the sticks in a straight line such that

Cutting Sticks UVA - 10003 (区间Dp)

链接：点击打开链接题目大意：有一根木棍长度为L，然后有N个切割点，将木棍切割成n+1段，当切割长度为Li时，那么需要Li的费用.例如有一个长度为10的木棍，切割点在2,4,7位置上，如果顺序切割的话： 1、首先长度为10，在2位置切割，那么sum+=10 2、再在剩下的长度为8的长度中切割4位置，那么sum+=8 3、再在剩下长度为6中切7位置，那么sum+=6==24 而如果按顺序

杭电OJ 1051:Wooden Sticks

这个题目的大意是有一个处理木材的机器，处理第一根木材的时候需要调整，后面的木材如果长度不小于前面的木材并且重量也不小于前面的木材则机器不需要重新调整，否则就需要调整，调整一次花费的时间为1，问机器最少要调整几次？这个问题其实可以转换为求最长递减子序列。转化过程：先对多所有的木材按长度从小到大排序，然后按重量求最长递减子序列，子序列元素的个数就是机器要调整的次数，因为这个序列中的元素是不可能排在

POJ 1011--Sticks

题目：这是题目题意：给你一些切断了的木棍，求原木棍的长度，长度尽可能小，数目不限。思路：爆搜，但是会T，要有一些处理。 1. 木棍从大到小排序，因为你总是要把长的和短的先拼凑的，相同的木棍如果一根不行，那后面相同的也肯定不行。 2. 要拼凑当前的木块肯定是从它后面的木棍开始找，因为如果这个木棍没有被拼凑那么它肯定是因为前面的用不到它，所以只要从它后面的木棍开始找 3. 如果一个木棍和

POJ 2513 Colored Sticks(字典树+欧拉路径)

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11158 Colored Sticks Time Limit: 5000MS Memory Limit: 128000KB 64bit IO Format: %I64d & %I64u Submit Status Description

UVa 11686 Pick up sticks (BFS拓扑排序)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2733 算是一种模板题吧。。两个发现： 1. 重复初始化queue相当费时间！最好只声明一次queue！ 2. 能不用iterator就不用，这个也相当费时间！完整代码： /*0

Game With Sticks

最近思维实在是不活跃。。。。。。题目链接：Submit - Codeforces 解题思路：如果n > m,交换直接判断n就行，偶数M赢，奇数A赢下面是c++代码： #include<iostream>using namespace std;int main(){int n, m;cin >> n >> m;if (n > m) {n = n ^ m;m = n ^

Sticks Problem POJ - 2452

http://poj.org/problem?id=2452 单调栈找出每个数a[i]右边第一个小于等于他的数在哪记为pos[i] 然后在[i,pos[i]-1]内找一个最靠左的最大值在哪记为p 则[i,p]即为所求 #include <cstdio>#include <stack>#include <cstring>#include <algorithm>using namesp

hdu 1455 Sticks（DFS+剪枝）

原题链接： hdu 1455 题目大意： n个木棒，求原来木棒最短的长度（每个木棒等长且在数量上无限制，木棒可以未被折断过）。思路： DFS。三个参数，当前长度，当前遍历位置，当前已构成最短长度的个数。注意剪枝。从大到小排序，可以减少递归次数，不难理解。详见代码： #include<iostream>#include<cstdio>#

POJ 2513 Colored Sticks(trie 欧拉通路并查集)

这个题目只要想是欧拉通路那么基本上就搞定了判断偶拉通路就是度为奇数的点为0个或者2个用trie树来做检索为颜色编号工作然后用并查集判断一下图是否联通就基本上没问题了！ #include <iostream>#include <stdio.h>#include <string.h>using namespace std;struct trie{trie *next[

Lintcode 1872 · Minimum Cost to Connect Sticks [Python]

题目在下方。读题目，有点儿费解，但是基本思路就是每次选择最小的棍子和第二小的棍子，加起来，丢回棍子堆里，然后继续重复，直到只剩下一个整的棍子。很容易想到用堆。 import heapqclass Solution:"""@param sticks: the length of sticks@return: Minimum Cost to Connect Sticks"""def Minimum

【uva307】小木棍 Sticks [dfs搜索]

UVA307 小木棍 Sticks 我枯辽然后导致一直爆炸，就是调试一直就跳回初始状态然后就输出sum 我的一上午就这样么得了还有关于小蓝书上面的程序是错但剪枝是真的阔以就是有一些奇奇怪怪我看不懂的剪枝关于剪枝 sum一定能被原长度整除木棍的长度一定大于等于所有木棍中最长的那一根将木棍长度从大到小排因为拼长度为a b的两个木棍 ab和ba的先后顺序是等效的只需要搜索其中一种

uva 10003 Cutting Sticks

题意：有根木头，长度l，对它切n刀，分别在c1,c2....cn位置。费用等于你当前切的木头的长度。问你最少的费用是多少。定义dp(be,end)为从切点be到end的最少费用。 #include <iostream>#include <cstdio>#include <cstring>using namespace std;const int N=60;int a[N],ma

例题9-9 UVa10003 Cutting Sticks（DP：矩阵链乘）

题意：看白书要点：明显是类似于矩阵连乘问题，用d[i][j]标记i到j中的最优费用，从中间一点k处截成两半，可以写出状态转移方程为d[i][j] = min(d[i][j], d[i][k] + d[k][j] + pos[j] - pos[i])，不难看出这实际是一个区间DP问题，通过j-i小区间不断递增进行DP，注意这里i和j不用写成0~len，因为d[i][j]只是起到一个存储状

POJ 2653 Pick-up sticks 线段交

直接暴力即可，因为题目中说了top line不超过1000个。所以理论复杂度不会非常大 #include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#

pku 2455 Sticks Problem

这道题是月赛题，有解题报告的。用的是分治的做法。当时想到了，但总感觉有点不够完美，所以没做，原来是没有正确估算时间复杂度…… #include <iostream>#include <algorithm>#define N 50001using namespace std;int n;int a[N];int b[N];int bst;void getLong(int l

Sticks//拼火柴//Central Europe 1995//dfs

Sticks//拼火柴//POJ - 1011//dfs 题目 George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but h

UVA 10003 切木棍 Cutting Sticks

切木棍 Cutting Sticks 题面翻译翻译有一根长度为L（L＜1000）的棍子，还有n（n＜50）个切割点的位置（按照从小到大排列）。你的任务是在这些切割点的位置处把棍子切成n＋1部分，使得总切割费用最小。每次切割的费用等于被切割的木棍长度。例如，L=10，切割点为2, 4, 7。如果按照2, 4, 7的顺序，费用为10＋8＋6=24，如果按照4, 2, 7的顺序，费用为1