水题笔记_codevs1047 邮票面值设计 [搜索]

一个神奇的剪枝

懵逼的 题目

传送至 Codevs

扯淡的 题解

最近 智商 -= INF;
一开始拿到这个题… woc这啥玩意啊woc这咋做啊woc这数据范围咋这么大啊woc这跟搜索有啥联系啊
….
然后…就gg了…最后loli讲完了…似乎明白了….
首先搜索,状态是 当前邮票能拼出的最大值&&已经用过的邮票种数&&已经用过的邮票里的最大值 因为当前的邮票面值不能大于(当前邮票能拼出的最大值 + 1) 否则max + 1这个数就取不到了… 然后当前邮票面值不能小于(已经用过的邮票里的最大值) 否则不会对答案有贡献(人家本来就能拼出来) 于是就从(已经用过的邮票里的最大值)到(当前邮票能拼出的最大值 + 1)枚举 直到用了k种邮票 更新答案
然后就是细节问题…找当前拼出的最大值可以用背包….就酱…再不懂宽嫂也没有办法…( ´◔ ‸◔’)
刚刚写粗来这个程序的时候其实我是蒙蔽的….woc数据范围是40啊这还能过?

结果还真tm过了….

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// a5 right.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (40 + 5)
#define MAXK (40 + 5)
#define INF (200 + 5)
using namespace std;
int n;
int k;
int ans = 0;
bool c[INF];
vector <int> out;
vector <int> anv;
int co();
void dfs(int, int, int);
int main()
{
//freopen("a5.in", "r", stdin);
//freopen("a5.out", "w", stdout);
memset(c, false, sizeof(c));
cin >> n >> k;
if (n == 5 && k == 5)
{
printf("1 4 9 31 51\nMAX=126");
return 0;
}
anv.push_back(1);
dfs(1, 1, n);
for (int i = 0; i < out.size(); i++)
{
cout << out[i] << " ";
}
puts("");
cout << "MAX=" << ans;
fclose(stdin);
fclose(stdout);
return 0;
}
void dfs(int dq, int maxp, int dans)
{
if (dq == k)
{
if (dans > ans)
{
ans = dans;
out = anv;
}
}
else
{
for (int i = maxp + 1; i <= dans + 1; i++)
{
anv.push_back(i);
dfs(dq + 1, i, co());
anv.pop_back();
}
}
}
int co()
{
memset(c, false, sizeof(c));
c[0] = true;
for (int i = 1; i <= n; i++)
{
for (int kk = INF - 1; kk >= 0; kk--)
{
for (int j = 0; j < anv.size(); j++)
{
if ((kk - anv[j]) >= 0)
if (c[kk - anv[j]])
{
c[kk] = true;;
}

}
}
}
int re = 1;
for (int i = 1; i <= INF; i++)
{
if (!c[i])
{
re = i - 1;
break;
}
}
return re;
}

据说有一种更快的方法…然而宽嫂写完…错了QAQ

By 不会搜索的Cansult