ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[洛谷P1021][NOIP1999 提高组] 邮票面值设计(DP + DFS)

2022年4月5日 1021点热度 0人点赞 0条评论

题目传送门:P1021 [NOIP1999 提高组] 邮票面值设计 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

显然是个搜索,但是如果直接暴力搜索的话,肯定会TLE,所以需要一个搜索的区间。

假设已经得到了前dep种票的面值,且一共有N张,那么为了保证面值之和的连续性下一张票的面值可能是哪些呢?可能是上一张票面值 + 1 直到 前dep种票所能组成的最大数字 + 1(这个右边界会偏大一点点,但是影响并不大)。

为了得到这个N张dep种票能够组成的连续的最大的数,需要用到dp,也就是一个简单的背包问题。

dp[j]表示到前i种票为止,组成面值为j的所需的最小票的数量。如果一个面值j的所需最小数量 > N的话说明这个面值无法通过这dep种票组成。

状态转移方程:

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5010;
int N, K;//N张,K种 
int ans = 0;
int t[maxn],a[maxn];//t临时,a答案 

int f(int dep,int sum)
{
	int dp[maxn];memset(dp, 1, sizeof dp);
	dp[0] = 0;
	//dp[i]表示用前dep张票凑出i面值需要多少张票 
	for(int i = 1;i <= dep; ++ i)
		for(int j = t[i];j <= N * sum; ++ j)
			dp[j] = min(dp[j], dp[j - t[i]] + 1); 
		
	for(int i = 1;i <= N * sum; ++ i)if(dp[i] > N)return i - 1;
	return N * sum;
}

void dfs(int dep,int s,int sum)//dep表示层数,也表示到达了第几种票 
{
	int r = f(dep, sum);
	if(dep > K)
	{
		if(r > ans)
		{
			for(int i = 1;i <= K; ++ i)a[i] = t[i];
			ans = r;
		}
		return ;
	}
	//l表示上一张票的面值,r表示右边界 
	for(int i = s + 1;i <= r + 10; ++ i)//遍历面值 
	{
		t[dep] = i;//记录第dep张票面值为i 
		dfs(dep + 1, i, sum + i);
	}
}

signed main()
{
	cin >> N >> K;
	dfs(1, 0, 0);
	for(int i = 1;i <= K; ++ i)printf("%lld%c",a[i],i == K ? '\n' : ' ');
	printf("MAX=%lld\n",ans);
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ dfs DP 动态规划 提高组 洛谷
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 思路
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号