★Stamps 郵票
已知一個 N 枚郵票的面值集合（如,{1 分,3 分}）和一個上限 K —— 表示信封上能夠貼 K 張郵
票.計算從 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 分的郵資.因此,對于這兩種郵票的集
合和上限 K=5,答案是 M=13.
PROGRAM NAME: stamps
INPUT FORMAT
第 1 行: 兩個整數(shù),K 和 N.K（1 <= K <= 200）是可用的郵票總數(shù).N（1 <= N <= 50）是郵票面
值的數(shù)量.

第 2 行 .. 文件末: N 個整數(shù),每行 15 個,列出所有的 N 個郵票的面值,面值不超過 10000.

這題跟丑數(shù)很像模仿著寫就行了。我一開始以為湊一個數(shù)從大到小湊就一定需要的個數(shù)最小后來發(fā)現(xiàn)錯了。

所以用c數(shù)組記錄狀態(tài)。（這個數(shù)是由幾張郵票組成的）

一開始完全模仿丑數(shù)開了兩個2000000的數(shù)組結(jié)果超內(nèi)存，為什么這么點都超內(nèi)存。。。。一個就不超了

cmp可以去掉因為從大到小與從小到大排數(shù)組跟我們結(jié)果沒關(guān)系

/*
ID: jinbo wu
TASK:stamps
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
int b[55];
int cnt[55];
int c[2000010]; 
bool cmp(int a,int b)
{return a>b;
}
int main()
{freopen("stamps.in","r",stdin);freopen("stamps.out","w",stdout);int k,n,m;cin>>k>>n;int ans;for(int i=0;i<n;i++)cin>>b[i];sort(b,b+n,cmp);int i;for(i=1;;i++){m=INF;for(int j=0;j<n;j++){if(i<b[j])continue;c[i]=c[i-b[j]]+1;m=min(c[i],m);}c[i]=m;if(c[i]>k){ans=i-1;break;}}printf("%d\n",ans);
}

總結(jié)

以上是生活随笔為你收集整理的usaco ★Stamps 邮票的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。