【题解-洛谷】P2725 [USACO3.1] 邮票 Stamps

题目P2725 [USACO3.1] 邮票 Stamps题目描述给一组n nn枚邮票的面值集合和一个上限k kk—— 表示信封上能够贴k kk张邮票。请求出最大的正整数m mm满足1 11到m mm的面值都可以用不超过k kk张邮票表示出来。输入格式输入的第一行是两个整数分别代表邮票上限k kk和邮票面值数n nn。自第二行起除最后一行外每行有15 1515个整数a i a_iai​最后一行的整数个数不超过15 1515共有n nn个整数第i ii个整数代表第i ii种邮票的面值a i a_iai​。输出格式输出一行一个整数代表m mm。若m mm不存在请输出0 00。输入输出样例 #1输入 #15 2 1 3输出 #113说明/提示样例输入输出 1 解释有1 11分和3 33分的邮票你最多可以贴5 55张邮票。很容易贴出1 11到5 55分的邮资用1 11分邮票贴就行了接下来的邮资也不难6 3 3 6 3 3633。7 3 3 1 7 3 3 17331。$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 13 3 3 3 3 11333331。然而使用5 55枚1 11分或者3 33分的邮票根本不可能贴出14 1414分的邮资。因此答案为13 1313。数据规模与约定对于100 % 100\%100%的数据保证1 ≤ k ≤ 200 1 \leq k \leq 2001≤k≤2001 ≤ n ≤ 50 1 \leq n \leq 501≤n≤501 ≤ a i ≤ 10 4 1 \leq a_i \leq 10^41≤ai​≤104。说明题目翻译来自 NOCOW。思路原思路本来是将面额看成价值每个邮票的体积看成1求前n个数量不超过k的邮票能表示的最大面额。由于本题要求的是能表示出的所有面额所以将f[i-1][j-kv]kw的值看作下标建立了bool数组。但是这样做的话前一个状态是最大面额即使枚举了当前第i个邮票的数量还是没办法表示出所有可取的面额。现思路将面额看作体积每个邮票的价值看成1求前n个面额不超过k*maxv的邮票所需要的最小数量。代码一维数组#includebits/stdc.husingnamespacestd;typedeflonglongLL;constintN5010,M2e610;LL n,k,V,w1,v[N],f[M],maxv;boolflag;intmain(){cinkn;for(LL i1;in;i){cinv[i];maxvmax(maxv,v[i]);}Vk*maxv;memset(f,0x3f,sizeoff);f[0]0;for(inti1;in;i)for(intjv[i];jV;j)f[j]min(f[j],f[j-v[i]]w);for(intj1;jV;j)if(f[j]k){if(j1)coutj-1;elsecout0;flagtrue;break;}if(!flag)coutV;return0;}结果