该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

二、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（购票问题）儿童节到了，公园的售票处排起了长龙。按售票处规定，每位购票者限购一张门票，每张门票售价50元。现在有n个人手持50元排队，有n个人手持100元排队。假设售票处在开始售票的时候没有零钱，试问这2n个人有多少种排队方式可以使售票处不会出现找不开钱的尴尬局面。 例如当n = 2时，可以有 50 100 50 100，50 50 100 100 这两种排队方式。 试补全模拟程序。

#include <iostream>
using namespace std;
typedef long long LL;
LL k,sum,n;
void dfs(int dep)
{
	if (①)
	{
		if (②) sum++;
		return;
	}
	if (③)
	{
		④
		dfs(dep + 1);
		⑤
	}
	k++;
	dfs(dep + 1);
	k--;
}
int main()
{
    scanf("%lld",&n);
    k = 0;
    sum = 0;
    dfs(0);
    printf("%lld",sum);
    return 0;
} 

1.①处应填（ ） {{ select(1) }}

• dep == n
• dep == 2 * n
• dep > 2 * n
• dep > n

2.②处应填（ ） {{ select(2) }}

• !k
• dep == 2 * n
• k != 0
• sum == 0

3.③处应填（ ） {{ select(3) }}

• sum > 0
• k > 0
• k >= 0
• dep >= 0

4.④处应填（ ） {{ select(4) }}

• k++;
• k--;
• sum++;
• dfs(dep – 1);

5.⑤处应填（ ） {{ select(5) }}

• k++;
• k--;
• sum--;
• return;

（2）（括号配对问题）

合法的括号串定义如下：

空表达式是合法的

如果表达式A是合法的，那么(A)与[A]都是合法的

如果A和B都是合法的，那么AB也是合法的

下面给你一个字符串，求至少添加多少个字符能使这个字符串合法。

（给定的字符串仅由‘(’、 ‘)’ 、‘[’、 ‘]’这四个字符组成）

试补全模拟程序。

01	#include <bits/stdc++.h>
02	using namespace std;
03	const int N = 110, INF = 1e8;
04	char s[N];
05	int f[N][N];
06	bool check(char a, char b)
07	{
08	    if (a == '(' && b == ')') return true;
09	    if (a == '[' && b == ']') return true;
10	    return false;
11	}
12	int main()
13	{
14	    scanf ("%s", &s);
15	    int n = strlen(s);
16	    for (int len = 1; len <= n; len ++ )
17	        for (int l = 0;①; l ++ )
18	        {
19	            int r = len + l - 1;
20	            ②;
21	            if (check(s[l], s[r])) f[l][r] = ③;
22	            f[l][r] = min(f[l][r], min(④, f[l][r - 1]) + 1);
23	
24	            for (int k = l; k < r; k ++ )
25	                f[l][r] = min(f[l][r], f[l][k] + ⑤);
26	        }
27	    printf("%d\n", f[0][n - 1]);
28	    return 0;
29	}

1.①处应填（ ） {{ select(6) }}

• l < n && l < len
• l + len - 1 <= n
• l + len - 1 < n
• l < n

2.②处应填（ ） {{ select(7) }}

• f[l][r] = 0;
• f[len][r] = 0;
• f[l][r] = INF;
• f[l - len][r - len] = INF;

3.③处应填（ ） {{ select(8) }}

• 1
• INF
• f[l – 1][r + 1]
• f[l +1][r - 1]

4.④处应填（ ） {{ select(9) }}

• f[l + 1][r – 1]
• f[l – 1][r]
• f[l][r + 1]
• f[l + 1][r]

5.⑤处应填（ ） {{ select(10) }}

• f[k + 1][r]
• f[k][r]
• f[k + 1][r - 1]
• f[k][r - 1]