Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.
For example, consider stamps whose values are limited to 1 cent and 3 cents; you can use at most 5 stamps. It's easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren't much harder:
- 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.
However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13.
The most difficult test case for this problem has a time limit of 3 seconds.
PROGRAM NAME: stamps
INPUT FORMAT
Line 1: | Two integers K and N. K (1 <= K <= 200) is the total number of stamps that can be used. N (1 <= N <= 50) is the number of stamp values. |
Lines 2..end: | N integers, 15 per line, listing all of the N stamp values, each of which will be at most 10000. |
SAMPLE INPUT (file stamps.in)
5 2 1 3
OUTPUT FORMAT
Line 1: | One integer, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set. |
SAMPLE OUTPUT (file stamps.out)
13
题意:
给出 K(1 ~ 200) 和 N(1 ~ 50),代表只能使用任意的 K 个数,有 N 种数选择,后给出 N 个数,输出一个最大的上限,使凑到 1 ~ M 中的任意一个数,只能用 K 个数且必须是 N 种数里面。
思路:
DP。dp [ i ] 代表能凑到 i 钱币的最少使用张数,当一遇到凑不到的情况就退出循环。
递推式子 dp [ i ] = min { dp [ i ] , dp [ i - mon [ j ] ] + 1 }。
AC:
/* TASK:stamps LANG:C++ ID:sum-g1 */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 3000005; const int INF = 9999999; int dp[MAX], mon[55]; void init() { for (int i = 0; i < MAX; ++i) dp[i] = INF; dp[0] = 0; } int main() { freopen("stamps.in", "r", stdin); freopen("stamps.out", "w", stdout); init(); int k, n; scanf("%d%d", &k, &n); for (int i = 0; i < n; ++i) scanf("%d", &mon[i]); for (int i = 1; i < MAX; ++i) { for (int j = 0; j < n; ++j) { if (i - mon[j] >= 0 && (dp[i - mon[j]] + 1) <= k) { dp[i] = min(dp[i], dp[i - mon[j]] + 1); } } if(dp[i] == INF) { printf("%d\n", i - 1); break; } } return 0; }
相关推荐
StaMPS较新的版本,增加了SBAS算法
StaMPS软件操作流程.docx
StaMPS/MTI Manual Version 3.3b1 基于StaMPS的PS时序分析 、SBAS时序分析
stamps hooper v 4.01 pdf
永久性散射体开源软件StaMPS4.1版本详解 教程全套
结合SNAP和StaMPS软件获取地表时间序列形变
StaMPS软件操作流程.doc
北大ACM-POJ1010 - STAMPS 原比赛(Pacific Northwest 1998)题目的测试数据
StaMPS开源软件4.1版本 带使用手册
合成孔径雷达干涉测量ps-insar软件stamps操作说明书
StaMPS软件教程中文版
manual of stamps hooper
北大POJ1010-STAMPS 解题报告+AC代码
zoj 1812 Stamps.md
snap2stamps 使用SNAP作为StaMPS的InSAR处理器 本手册和随附的脚本调用ESA SentiNel应用程序平台(SNAP)的例程,以在开源StaMPS软件包中进行摄取的情况下执行TOPSAR干涉测量处理。 SNAP to StaMPS手册随附的...
针对DIn SAR技术易受时空失相关、大气相位延迟等影响的问题,采用Sta MPS方法对12景ALOS PALSAR数据进行时序处理。首先获取了采动区边缘区域2012-2014年的非线性时序沉降量,在工作面边缘地区走向方向和倾向方向各选取...
StaMPS-斯坦福永久散射体方法 描述 StaMPS是一个软件包,可以从合成Kong径雷达(SAR)采集的时间序列中提取地面位移。 该软件包结合了持久散射和小型基线方法,以及将两种方法结合在一起的选项。 它与TRAIN软件兼容...
这是一道典型的动态规划题 提供了三种方法(用C++代码实现)
StaMPS软件操作作业流程.doc