发表于 | 更新于 |

题目链接：http://poj.org/problem?id=1700

思路引用自https://blog.csdn.net/u014492609/article/details/40918435

当n=1,2,3时所需要的最小时间很容易求得,现在由n>=4,假设n个人单独过河所需要的时间存储在数组t中,将数组t按升序排序,那么 这时将单独过河所需要时间最多的两个旅行者送到对岸去,有两种方式:

  1. 最快的(即所用时间t[0])和次快的过河,然后最快的将船划回来,再次慢的和最慢的过河,然后次快的将船划回来。即所需时间为:t[0]+2*t[1]+t[n-1]
  2. 最快的和最慢的过河,然后最快的将船划回来,再最快的和次慢的过河,然后最快的将船划回来,即所需时间为:2*t[0]+t[n-2]+t[n-1]

注意这两种过河方式是两种最优的过河方式，每一次过河都应该判断具体采用哪一种。

阅读全文 »

发表于 | 更新于 |

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6188

一个对子只消耗两张牌，相对于顺子更加「实惠」。考虑这样一个贪心策略：先把每种牌能换成对子就换成对子，此时每种牌一定只有一张或零张。对于一种牌i，如果i有一张，且i+1也有一张，那么只要i+2初始时有牌就把i，i+1，i+2换成一个顺子，这样做最多是一个对子换顺子，而且可能会在i+2的位置多留出一张牌。

阅读全文 »

发表于 | 更新于 |

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1051

贪心策略，按照l为第一关键字，w为第二关键字排序，在排序后的w数组中寻找不下降子序列的个数即可（因为此时l数组单调不下降一定满足题目条件）。
有一个结论：单调不下降（不上升）子序列的数目等于最长单调下降（上升）子序列的长度，用树状数组求解LIS即可。
LIS问题用树状数组求解，树状数组直接维护前i-1个序列元素的LIS的最大值，树状数组的下标对应序列元素的高度（这样可以直接查询高度大于(等于)或小于(等于)个高度的LIS的最大值），序列下标较小的元素先进树状数组，保证了树状数组里查询到的结果一定是前i-1个元素而非之后的元素的。
看到这题的n为5000，感觉n^2肯定会炸，就写了一个LIS，结果发现其实交一个暴力的话只需要15ms，心情复杂.jpg

阅读全文 »

发表于 | 更新于 |

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3415

这题乍一看是区间最大子段和加上了长度的限制。
维护一个前缀和b[n]，枚举i，对于当前i，显然最优解是b[i]-min(b[l])，其中i-k<= l <=i-1。
此时只需要能快速找出b[l]即可。
考虑每次只需要找到满足位置要求（l的要求）的之前一段到当前位置的最小值，我们可以用单调队列来维护这个最小值。
这里维护一个单增的单调队列，每次取最小值时从队首找到第一个符合位置要求的值即可。

阅读全文 »

发表于 | 更新于 |

题目链接：http://codeforces.com/problemset/problem/578/C

可以看出weakness-x是一个单峰函数，可以使用三分。
然后就是求区间最大子段和。简化问题这里假设只求正最大子段和，dp[i-1]转移到b[i]时，不论b[i]是正是负，若dp[i-1]是正则一定会对它产生“正面影响”，此时dp[i]=dp[i-1]+b[i]；若dp[i-1]是负则一定会对b[i]产生“负面影响”，此时应该扔掉dp[i-1]，dp[i]=b[i]。
题目要求求出正负最大子段和，这里只需要对b[i]求一遍正最大子段和，再把b[i]取反，再求一遍最大子段和即可。

阅读全文 »

发表于 | 更新于 |

题目链接：http://codeforces.com/problemset/problem/287/B

稍加分析，题目可以转换成这样一个问题：给定1, 2, 3, …, k-1, 问它们的部分和是否能凑出n-1，如果能最少要用多少个数。
一种贪心的思想是寻找一个i，使得i, i+1, …, k-1的和大于等于n-1,在这个前提下要求i最大。此时有i+1, i+2, …, k-1的和小于n-1。回想要用最少的数凑出n-1，此时i+1, i+2, …, k-1是一定要选的，对应n-1减去它们的和后所余下的差r一定小于i+1（否则不满足i最大的要求），此时从1, 2, …, i中调出一个数补上即可。
此时对应的所需要的分流器为i+1到k所有分流器和1到i中的某一个分流器。
另外需要注意的是n=1的情况，由于二分没有判断结果是否合理，因此需要特判。

阅读全文 »