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

此非贪心,亦非动态

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

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

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 意为:

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,直接返回结果。

具体实现

/* 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 */

我的结果:

nil

总结

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