codeves天梯 邮票面值设计

本文主要是介绍codeves天梯 邮票面值设计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个信封，最多只允许粘贴N张邮票，计算在给定K（N+K≤40）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值MAX，使在1～MAX之间的每一个邮资值都能得到。

   

    例如，N=3，K=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，K=2时，7分就是可以得到的连续的邮资最大值，所以MAX=7，面值分别为1分、3分。

分析：一开始没什么头绪，后来看了下题解，其实这题的做法是dfs兼动态规划，做法就是每次先d出一个邮票的面值，在通过算总数的动态规划（很像01背包）进行统计更新。动态转移方程：f[i]:=max(f[i],f[i-a[i]]+1);

constmaxn=200;varf:array [0..maxn] of longint;a,n1:array [1..maxn] of longint;n,k,max:longint;procedure init;
vari,j:longint;
beginreadln(n,k);
end;function try(x:longint):longint;
vari,j:longint;
beginf[0]:=0;i:=0;repeatinc(i);f[i]:=maxint;for j:=1 to x doif a[j]>i thenbreakelseif f[i-a[j]]+1<f[i] thenf[i]:=f[i-a[j]]+1;until f[i]>n;exit(i-1);
end;procedure dfs(dep:longint);
vari,t:longint;
beginif dep>k thenbegint:=try(dep);if t>max thenbeginmax:=t;n1:=a;end;exit;end;t:=try(dep-1)+1;for i:=a[dep-1]+1 to t dobegina[dep]:=i;dfs(dep+1);end;
end;procedure work;
vari:longint;
begininit;a[1]:=1;dfs(2);for i:=1 to k dowrite(n1[i],' ');writeln;write(max);
end;beginwork;
end.

这篇关于codeves天梯 邮票面值设计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---