題目背景
給一組 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 張郵票貼出的郵資數。
輸入輸出樣例
輸入 #1
5 2 1 3
輸出 #1
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 }
浙公網安備 33010602011771號