哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

全部文章 / 未归档（共121篇）

Jury Compromise POJ - 1015 dp （标答有误）背包思想

题意:从 n个人里面找到m个人每个人有两个值 d p 满足在abs(sum(d)-sum(p)) 最小的前提下sum(d)+sum(p)最大思路：dp[i][j] i个人中和是 j 运用背包的思想二维背包 i是人数容量，人数要符合背包思想，每次只插入一个，...

2019-01-15

0 751

Paths on a Grid POJ - 1942 组合数学（组合数的快速计算）

题意：格路问题没什么难度难点在于如何快速计算相对较大的组合数思路：运用手写计算组合数的方式进行计算如c(8,3) 如果手算就是 8*7*6/(3*2*1)这样可以很快得解出计算代码为：(精度没问题? 反正能过) 1 u c(u n,u m){ 2 u a=n+...

2019-01-14

0 631

Code POJ - 1850 组合数学

　　题意：字符串从a=1 b=2 c=3....z=26 ab=27开始编号每个都是升序的给出字符串问是几号　　思路：主要是要看n位字符串有多少个这里需要用组合数学的思想组合数用杨辉三角形递推出　　参考：https://blog.csdn.net/lyy289...

2019-01-14

0 567

Number Sequence POJ - 1019 递推数学

　　题意 1 12 123 1234 12345 ....这样的序列问第n位数字是几是数字！ 1-9! 　　思路：递推关系主要是位数的计算用a[i]=a[i-1]+(int)log10((double)i)+1; 每加一个n位数加log10(n)+1位　　　　　　还有取...

2019-01-14

0 630

Joseph POJ - 1012 约瑟夫环递推

　　题意：约瑟夫环初始前k个人后k个人问m等于多少的时候后k个先出去　　题解：因为前k个位置是不动的，所以只要考虑每次递推后的位置在不在前面k个就行　　有递推式 ans[i]=(ans[i-1]+m-1)%(n-i-1) 其中i是轮数 ans[i]是i出局的位置出局后后面的补...

2019-01-12

0 416

Longest Ordered Subsequence POJ - 2533 最长上升子序列dp

题意：最长上升子序列nlogn写法 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace...

2019-01-12

0 526

Pearls POJ - 1260 dp

　　题意：有n种不同的珍珠每种珍珠的价格不同现在给出一个采购单标注了需要不同等级的珍珠和相对于的个数（输入按价格升序排列）　　其中价格为（当前种类价格+10）*购买数量这样就有一种诡异的现象，当你把购买x个低价格珍珠的时候可能还没有把x个低价格珍珠　　换成高价格珍珠来...

2019-01-12

0 383

复习 LIS nlogn

　参考：https://www.cnblogs.com/wxjor/p/5524447.html 　　最长下降只要把符号都倒过来就行在栈中二分找第一个比当前值小的替换就行

2019-01-12

0 392

The Cow Lexicon POJ - 3267 dp

　　题意给出一个母串和一个字典问母串最少删去几个字母删去后的母串是由字典里面的单词拼起来的　　思路：dp[i]表示从i到母串结尾最少需要删除多少个字母初始化dp[length]=0 最坏情况dp[i]=dp[i+1]+1 　　状态转移方程 dp[i]=min(dp[i]...

2019-01-12

0 445

Dividing POJ - 1014 多重背包二进制优化

多重背包模型写的时候漏了一个等号找了半天 i<<=1 ！！！！！！ 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespac...

2019-01-12

0 453