USACO - 3.1.6 - Stamps
http://qingtangpaomian.iteye.com/blog/1635988
一. 題目翻譯1. 描述： ??已知一個(gè) N 枚郵票的面值集合（如，{1 分，3 分}）和一個(gè)上限 K —— 表示信封上能夠貼 K 張郵票。計(jì)算從 1 到 M 的最大連續(xù)可貼出的郵資。 例如，假設(shè)有 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 分的郵資。因此，對(duì)于這兩種郵票的集合和上限 K=5，答案是 M=13。 [規(guī)模最大的一個(gè)點(diǎn)的時(shí)限是3s]
小提示:因?yàn)?4貼不出來,所以最高上限是13而不是15 。
2. 格式：
? ? ? ? ? INPUT FORMAT:
第 1 行： 兩個(gè)整數(shù)，K 和 N。K（1 <= K <= 200）是可用的郵票總數(shù)。N（1 <= N <= 50）是郵票面值的數(shù)量。 第 2 行 .. 文件末： N 個(gè)整數(shù)，每行 15 個(gè)，列出所有的 N 個(gè)郵票的面值，每張郵票的面值不超過 10000。??????????OUTPUT FORMAT:
??第 1 行：一個(gè)整數(shù)，從 1 分開始連續(xù)的可用集合中不多于 K 張郵票貼出的郵資數(shù)。3. SAMPLE： ??????????SAMPLE INPUT: 5 2 1 3 ??????????SAMPLE OUTPUT: 13
? ? ? ? ?? 二. ?題解
1. 題意理解（將問題分析清楚，大致用什么思路）： 這道題目還是可以使用動(dòng)態(tài)規(guī)劃的，我們使用一個(gè)數(shù)組needs[i]表示產(chǎn)生面值為i的郵資需要的最少的郵票數(shù)量。然后遍歷needs[i]，如果needs[i]大于我們輸入的最大可使用的郵票數(shù)量，則輸出i-1為滿足要求的最大面值。
?
2.?具體實(shí)現(xiàn)（具體實(shí)現(xiàn)過程中出現(xiàn)的問題）： 狀態(tài)轉(zhuǎn)移方程如下needs[i] = min {needs[i] , needs[i-prize[k]]+1}(k=1..N)。具體實(shí)現(xiàn)請(qǐng)參考代碼。
下面是上面題的升級(jí)版
http://sfiction.blog.163.com/blog/static/1994040102012520113738298/
給定一個(gè)信封，最多只允許粘貼N張郵票，計(jì)算在給定K種郵票的情況下（假定所有的郵票數(shù)量都足夠），如何設(shè)計(jì)郵票的面值，能得到最大max，使得1-max之間的每一個(gè)郵資值都能得到。
例如，N=3，K＝2，如果面值分別為1分、4分，則在l分-6分之間的每一個(gè)郵資值都能得到（當(dāng)然還有8分、9分和12分）：如果面值分別為1分、3 分，則在1分-7分之間的每一個(gè)郵資值都能得到。可以驗(yàn)證當(dāng)N=3，K＝2時(shí)，7分就是可以得到連續(xù)的郵資最大值，所以max=7，面值分別為l分、3 分。
[數(shù)據(jù)范圍]
100%的數(shù)據(jù)，N + K <= 14
這道題真是混蛋……開始是動(dòng)態(tài)規(guī)劃沒寫全WA了兩次，修正以后無數(shù)2B錯(cuò)誤連WA三次，唯一的欣慰就是最優(yōu)解排在第七。
DFS+DP。DFS枚舉所有可能的構(gòu)造方式，用背包解決0..M的面值用當(dāng)前郵票湊出的最小代價(jià)。
/* ID: Sfiction OJ: RQNOJ PROB: 112 */ #include <stdio.h> #define M 500 int a[20],f[M],ans[20]; int N,K,MAX,g=1<<29; void DFS(int k,int s) {int i,j,t[M];if (k==K){if (s>=MAX)for (MAX=s,i=1;i<=K;i++) ans[i]=a[i];return;}for (i=0;i<M;i++) t[i]=f[i];for (i=a[k]+1;i<=s;i++){for (j=0;j<M-i;j++)if (f[j]+1<f[j+i]) f[j+i]=f[j]+1;for (j=s;f[j]<=N;j++);a[k+1]=i;DFS(k+1,j);for (j=0;j<M;j++) f[j]=t[j];} } int main() {int i;scanf("%d%d",&N,&K);a[1]=1;for (i=1;i<=N;i++) f[i]=i;for (;i<M;i++) f[i]=g;DFS(1,N+1);for (i=1;i<=K;i++) printf("%d ",ans[i]);printf("\nMAX=%d",MAX-1);return 0; }
總結(jié)
以上是生活随笔為你收集整理的USACO - 3.1.6 - Stamps的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
