蓝桥杯算法训练VIP-邮票

题目

题目链接

题解

动态规划。

整体思路： dp[i]表示构成价值为i至少需要多少张； 从1开始从小到大遍历全部价值，若中途存在一种价值无法在使用不超过n张的前提下构成，则说明从此断开，输出这个数-1即可。 每一个大价值都是由小价值构成，转移方程为：dp[i] = min(dp[i], dp[i-j] + dp[j])，j=1~i-1； 既然能遍历到价值i说明价值1~i-1都是可以在使用不超过n张的前提下构成。想要构成价值i，就遍历之前的全部价值，看看最小需要多少张，赋值给dp[i]。

代码

#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e4+10;

int n, m, mx, mn, x, dp[N];

int main()
{
	cin>>n>>m;
	mn = INF;
	memset(dp, 0x3f, sizeof dp);
		
	for(int i = 0;i >x, dp[x] = 1, mx = max(mx, x), mn = min(mn, x);
	
	if(mn != 1) {cout