DFS插缝法(C++)

解题思路:在每个数字字符之间放入一个空位，利用dfs算法将k个'*'放入这些空位中。

注意事项:当x>=2*n时，cnt！=k，则'*'并未全部放入，要直接返回

参考代码:

#include <iostream>

#include <algorithm>

using namespace std;

int n, k;

char s[85] = { '.' };

int ans = 0;

int p, q;

void dfs(int x,int cnt) {     //x表示在空格在是s数组中位置，cnt表示放入的‘*’数；

if (x >= 2 * n && cnt != k)return;

if (cnt == k) {

p=0, q=1;

for (int i = 1; i < 2 * n; i++) {

if (s[i] <= '9' && s[i] >= '0') {

p = p * 10 + s[i] - '0';

}

if (s[i] == '*') {

q = q * p;

p = 0;

}

if (i == 2 * n - 1) {

q = q * p;

p = 0;

}

}

ans = max(q, ans);

return;

}

for (int i = x; i <2*n; i=i+2) {

if (s[i+1]=='0')continue;

s[i] = '*';

dfs(i+2, cnt+1);

s[i] = '.';

}

}

int main() {

cin >> n >> k;

for (int i = 1; i < 2*n; i++) {

cin >> s[i];

i++;

}

for (int i = 1; i <= n - k; i++) {

dfs(2 * i, 0);

}

cout << ans;

return 0;

}