题目传送门: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; }
Comments NOTHING