我的计划就从NOI1997开始。NOI1997一共有6道题，分别是[卫星覆盖][积木游戏][竞赛排名][最佳游览][最优乘车][文件匹配]。这一年的6个题难易分布均衡，做完后收获不小。
其中[竞赛排名]和...
|
|||||
|
动态规划，设F[i,j]为范围1..i的集合元素之和大于等于j，不含连续自然数的集合个数 由于可能存在空集的情况，即计算过程中出现了k=-1，这是很不方便的，所以我修改了定义，把大于k... 标准的广度优先搜索，哈希判重。由于无法估计状态数，需要用链队列存储搜索状态。把初始状态加入队列，然后取出队列中的首元素，对其状态进行扩展。判断不能有重复，否则是多余的... O(N^3)的枚举是无法忍受的，这道题可以从反面考虑。单色三角形的个数就是全部的三角形的个数减去不同色三角形的个数。 在一个不同色的三角形中，显然有两个顶点，每个顶点连着这... 提供一个没有优化的O(N^2)的动态规划解法。首先对所有的演讲时间区间按结束时间从小到大排序，然后设定状态。 S[i].l和S[i].r分别表示第i个演讲的开始和结束时间。 居然看到有人写的是一般图的最大匹配，其实排序就行了。设定两个游标i,j，i指向最小的元素，j指向最大的元素。如果i和j指向的元素之和小于等于船的载重，那么这两个人使用一个船，否... 这是一个思路新颖的动态规划问题，一看道题的时候看起来像搜索，一时没有想出动态规划。但是只要把思路变一下，要求给定的字串最少由几个S变换而成，每个自串能合成什么。 假...
|
|
||||
|
Copyright © 2010 Beyond the Void - All Rights Reserved
|
|||||