USACO/stamps

目前最快的时间

---

  Test 1: TEST OK [0.000 secs, 11992 KB]
  Test 2: TEST OK [0.000 secs, 11992 KB]
  Test 3: TEST OK [0.000 secs, 11992 KB]
  Test 4: TEST OK [0.000 secs, 11992 KB]
  Test 5: TEST OK [0.000 secs, 11992 KB]
  Test 6: TEST OK [0.000 secs, 11992 KB]
  Test 7: TEST OK [0.000 secs, 11992 KB]
  Test 8: TEST OK [0.000 secs, 11992 KB]
  Test 9: TEST OK [0.000 secs, 11992 KB]
  Test 10: TEST OK [0.028 secs, 11992 KB]
  Test 11: TEST OK [0.238 secs, 11992 KB]
  Test 12: TEST OK [0.056 secs, 11992 KB]
  Test 13: TEST OK [0.000 secs, 11992 KB]

---

目测较好的做法

---

（by volz.kz.g）

因为我们要找连续的一段数， 我们用F[I]记录构造出I大小面额所需要的邮票数量 因此可以从0开始，把0可以通过加一枚邮票扩展出来的全部扩展出来，然后去找1，把可以用1加一枚邮票扩展出来的面额找出来 详见C++代码volz.kz.g版本

---

官方题解(by Alex Schwendner)

一个简单的dp题目.我们开设数组minstamps.minstamps[i]表示凑成i分邮资所需要的最少邮票数.对于每一种邮票,我们试图在每一分我们已经贴出的邮资上再贴一张这种邮票.在我们找到贴出任何钱数所需要的最少邮票数,我们就寻找不能用所给的邮票数所能贴出的最少邮资.输出比它小1的数.

参考代码(见c部分)

---

动态规划的题目，用F[i]表示得到i面值所需要的最少邮票个数，Value[j](j=1..Stamps)表示每个邮票的面值，可得以下转移方程：

F[i]=Min ( F[i-Value[j]] + 1 ) (i-Value[j]>=0 j=1..Stamps)
初始状态：F[0]=0;F[i]=INFINITE;

如果计算中间某个F[i]大于了最大可以使用的邮票数量，则退出循环，输出i-1即为解

小优化： 初始化时先计算出最大面值的邮票，令其面值为MaxValue，然后在初始化F时可令：

F[k*MaxValue]=k;

这表示要得到k*MaxValue面值的邮票最少需要k张邮票，这是显然的。于是在计算时我们可以免去(1/MaxValue)*100%的运算量。 P.S. 很悲剧地，如果用官方算法，并且使用pascal，会有一个超时5%的点 PS:Pascal可以过，只是比较险，2.7s c++就好了，1.2s 所以pascal必须想着法子的优化

---

这个只要再背包的时候注意放入物品的顺序重复时不重复计算如（1，3）和（3，1）都可以得到4.注意不重复 所有数据都能在0.2s以下过掉。见代码1.

一个经过构思的优化

这个虽然是简单的DP题，只要是个优化都能过。但是经过考虑，本人认为排序后，能对 Test 11 这个点的效率进行很大的提升：

for i:=1 to n do
  if a[i]>a[i-1] then
    for j:=a[i] to a[i]*k do if rec[j]>rec[j-a[i]]+1 then 
      rec[j]:=rec[j-a[i]]+1;

排序后，就可以把DP的递推这样写，在大多数情况下是可以的。

详见Pacal的“不错的优化”。

给想不出来的菜鸟：一个经典、高效的优化思路

这题看着是一个比较典型的完全背包，然后我想出了以下状态转移方程：

（用f[]记录该面额能否组成（布尔型数组）,num[]记录组成该面额最少需要的邮票数，value[]记录每张邮票的价值,j表示面额，i表示第几张邮票）
f[j] = ( f[j-value[i]] ) or ( f[j] )  {num[j-value[i]]<k}
同时，如果f[j]=true 那么
if num[j-value[i]]+1<num[j] then num[j]=num[j-value[i]]+1
初始化时f[0]=true;num[]全部初始化为maxint

老实说，这一种状态转移方程思想比较像The Longest Prefix（Section 2.3，第一题）。

还记得那题吗？想想看我们当时怎么优化的？如果前面连续有单个最长元素的长度的字符失配那就跳出、输出结果。这一题也是同理——只不过是失配了继续考虑下一样物品而已。

只不过有一个严肃警告：如果想这样做，你必须把邮票的面额从小到大排序！（这个不难理解吧）

而且，如果用这种办法实现得好的话，效率还是出奇的好的：你可以比标准答案跑得快一些（Pascal），只不过内存是压线、压RP过的（幸好解不超过5*10^6，再大一些就玩完了，还需要考虑内存的优化）

Executing...
   Test 1: TEST OK [0.000 secs, 14924 KB]
   Test 2: TEST OK [0.000 secs, 14924 KB]
   Test 3: TEST OK [0.027 secs, 14924 KB]
   Test 4: TEST OK [0.000 secs, 14924 KB]
   Test 5: TEST OK [0.000 secs, 14924 KB]
   Test 6: TEST OK [0.000 secs, 14924 KB]
   Test 7: TEST OK [0.000 secs, 14924 KB]
   Test 8: TEST OK [0.000 secs, 14924 KB]
   Test 9: TEST OK [0.000 secs, 14924 KB]
   Test 10: TEST OK [0.054 secs, 14924 KB]
   Test 11: TEST OK [0.783 secs, 14924 KB]
   Test 12: TEST OK [0.054 secs, 14924 KB]
   Test 13: TEST OK [0.000 secs, 14924 KB]

All tests OK.

实现方法：

如果f[j-value[i]]=false 
{
  计数器++
  如果 计数器=value[i] {计数器清零、停止对i号邮票的判断}
  继续内层循环
}

代码参见Pascal，fcxxzux1

当然，内存还可以省下去，去掉布尔型数组，如果num[]中需要邮票为初始化的值（maxint）那就认为没有方案可以达到这个值——然后就转化为前面的那些方程了。（实测：内存瘦掉4MB，11号点时间再缩短0.1s左右）

BFS

这道题用BFS会很快 而且很容易实现 只是对于储存新拓展的节点时有点小要求 BFS拓展节点操作时只涉及到两层节点 所以在节点队列前头有很多已经完成拓展的节点 那么在拓展新节点时可以把前面的节点覆盖掉 这样优化队列数组开100000肯定够 详见代码 有人用BFS 最大一个点用不到1秒时间....

参考代码

C

C++

Pascal

Java

引用

[1]

[2]