题目: 1004. To Buy or Not to Buy - Hard Version (35)

此非贪心,亦非动态

当我第一次读完题目时,我天真的以为这道题不是 动态规划 就是 贪心

然而在我无数次思考其最优子结构后,发现这个最优子结构存不存在都没有关系!直接看下面这个状态转移公式:

1
2
A[0][j] = INFINITY
A[m][j] = min{A[m-1][j], A[m-1][j ^ (j&k)] + extra beads in m}

其中,m 表示 处理了前m个在商店中的beads ,而j 的二进制表示 010101011 意为:

1
2
if eva wants beads: YrRR8RRrY
now, we get beads `_r_R_R_rY`

所以,这种解决方式的复杂度为 2^n ,n 为 eva 想要的珠子数。这种非多项式的解法显然是没有意义的。

不过……其实题目并不需要保留原字符串字符的顺序,只要提取出各个字符的数量就可以了。 ∑(O _ O ;)

无脑DFS,适当减枝

思路很简单:

  1. 对每个 shopbeads (商店中的珠子串)进行深度优先搜索。
  2. 如果当先搜索项满足要求,则递归得对当前 shopbeads (此时它为parents)之后的每个 shopbeads (它们为children)进行深度优先搜索。
  3. 否则,结束当前 shopbeads 的搜索。

我们需要一个状态数据保存每次搜索完一个节点后的状态,并且 确保 children 的每个兄弟从 parents 中得到的状态数据是一样的 。当然,我们还需要一个全局变量来存储已经找到的结果。

最后,为了让它更快得运行,我们需要进行剪枝。具体如下:

  1. 在最初得到 shopbeads 数据时,就把不含 Eva 需要要的 beads 的数据项删除。
  2. 在满足 Eva 的需求后,停止对 children 的搜索。
  3. 在已得到最优解时( extra == 0 ),结束DFS,直接返回结果。

具体实现

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/* to buy or not buy --- introduction
*
* Maintainer: Mephis Pheies ( MephistoMMM )
* Email: mephistommm@gmail.com
*
* License:
* MIT License
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAXSTRINGS 100
#define CHARNUMBER 62
#define STRINGSLENGTH 1001

const char yes[] = "Yes", no[] = "No";

typedef int BeadDigital[CHARNUMBER];

typedef struct Note
{
BeadDigital beads;
// extra beads and missing beads
int extra, missing;
}Note;

int fmap(char c)
{

if(c >= '0' && c<= '9')
{
return c - '0';
}
if(c >= 'a' && c<= 'z')
{
return c - 'a' + 10;
}

//if(c >= 'A' && c<= 'Z')
return c - 'A' + 36;
}

void selfInspection(BeadDigital bd, char* s)
{

int len = strlen(s);
// self inspection
for(int i=0;i<len;i++) bd[fmap(s[i])]++;
}

short SubBeadsFromNote(Note *a, BeadDigital b)
{

// compute a->beads subtract b, saving the number of missing beads and
// extra beads
int missing = 0;
short useful = 0;
for(int i=0;i<CHARNUMBER;i++)
{
if(a->beads[i] == 0 && b[i] == 0) continue;
// b is unuseful while they have no common chars.
if(a->beads[i] != 0 && b[i] != 0) useful = 1;

if(a->beads[i]>b[i])
{
a->beads[i] -= b[i];
missing += a->beads[i];
}
else
{
a->extra += b[i] - a->beads[i];
a->beads[i] = 0;
}
}

a->missing = missing;
return useful;
}

int TestUseful(BeadDigital a, BeadDigital b)
{

short useful = 0;
for(int i=0;i<CHARNUMBER;i++)
{
if(a[i] != 0 && b[i] != 0)
{
useful = 1; break;
}
}

return useful;
}

void dfs(BeadDigital* shopbeads, int len, int j, Note a, Note *r)
{

// unuseful shopbeads is invalid
if(!SubBeadsFromNote(&a, shopbeads[j])) return;

if(a.missing == 0 && a.extra <= r->extra)
{
// get a better result
r->extra = a.extra; r->missing = 0;
return;
}
else if(a.missing < r->missing)
{
// get a less missing beads result
r->missing = a.missing;
}

// dfs search its children(the remaining shopbeads)
for(int i=j+1;i<len;i++)
{
// already get the optimal solution
if(r->extra == 0) return;
dfs(shopbeads, len, i, a, r);
}
}

void DFS(BeadDigital eva, BeadDigital* shopbeads, int len, Note *r)
{

Note a = {};
for(int i = 0;i<CHARNUMBER;i++) a.beads[i] = eva[i];
for(int i=0;i<len;i++)
{
// already get the optimal solution
if(r->extra == 0) return;
dfs(shopbeads, len, i, a, r);
}
}

int main()
{

BeadDigital eva = {};
BeadDigital shopbeads[MAXSTRINGS] = {};
Note result = {};

char s[STRINGSLENGTH]; int len;
scanf("%s\n%d", s, &len);
selfInspection(eva, s);

// init result
result.missing = strlen(s);
result.extra = INT_MAX;

int j=0;
for(int i=0;i<len;i++)
{
scanf("%s", s);
selfInspection(shopbeads[j], s);
// ignore unuseful shopbeads
if(TestUseful(shopbeads[j], eva)) j++;
}

len = j;
DFS(eva, shopbeads, len, &result);
if(result.missing == 0)
printf("%s %d\n", yes, result.extra);
else
printf("%s %d\n", no, result.missing);

return 0;
}
/* to buy or not buy ends here */

我的结果:

总结

这种暴力求解的题目真的很没意思,不明白为什么top level里会放这种题目。