洛谷 P2725 郵票題解

題目背景

給一組 N 枚郵票的面值集合（如，{1 分，3 分}）和一個上限 K —— 表示信封上能夠貼 K 張郵票。計算從 1 到 M 的最大連續可貼出的郵資。

題目描述

例如，假設有 1 分和 3 分的郵票；你最多可以貼 5 張郵票。很容易貼出 1 到 5 分的郵資（用 1 分郵票貼就行了），接下來的郵資也不難：

6 = 3 + 3 
7 = 3 + 3 + 1 
8 = 3 + 3 + 1 + 1 
9 = 3 + 3 + 3 
10 = 3 + 3 + 3 + 1 
11 = 3 + 3 + 3 + 1 + 1 
12 = 3 + 3 + 3 + 3 
13 = 3 + 3 + 3 + 3 + 1

然而，使用 5 枚 1 分或者 3 分的郵票根本不可能貼出 14 分的郵資。因此，對於這兩種郵票的集合和上限 K=5，答案是 M=13。 [規模最大的一個點的時限是3s]

小提示:因為14貼不出來,所以最高上限是13而不是15

輸入格式

第 1 行： 兩個整數，K 和 N。K（1 <= K <= 200）是可用的郵票總數。N（1 <= N <= 50）是郵票面值的數量。

第 2 行 .. 文件末： N 個整數，每行 15 個，列出所有的 N 個郵票的面值，每張郵票的面值不超過 10000。

輸出格式

第 1 行：一個整數，從 1 分開始連續的可用集合中不多於 K 張郵票貼出的郵資數。

輸入輸出樣例

5 2
1 3

13

說明/提示

題目翻譯來自NOCOW。

USACO Training Section 3.1

題解

這題雖然也是完全背包問題，但是比總分那題難想。直接選擇題目所求作為f[i]是不行的。f[i]為要達成i面值所需要的最少郵票個數。這樣狀態轉移方程就是：f[j] = min( f[j], f[j - a] + 1 );，也就是如果選擇面值為a可以減少張數就選擇a，否則不選a。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 #include <string.h>
 6 
 7 using namespace std;
 8 
 9 const int    MAXN = 2000005;
10 int        a, n, k, f[MAXN];
11 
12 int main()
13 {
14     cin >> k >> n;
15     for ( int i = 0; i < MAXN; i++ )
16     {
17         f[i] = 1111111;
18     }
19     f[0] = 0;
20     for ( int i = 1; i <= n; i++ )
21     {
22         cin >> a;
23         for ( int j = a; j <= MAXN; j++ )
24         {
25             if ( f[j - a] + 1 <= k ) /* 用的郵票數目在範圍內 */
26             {
27                 f[j] = min( f[j], f[j - a] + 1 );
28             }
29         }
30     }
31     for ( int i = 1; i < MAXN; i++ )
32     {
33         if ( f[i] == 1111111 )
34         {
35             cout << i - 1 << endl;
36             break;
37         }
38     }
39     return(0);
40 }