05 August 2008
给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 ’+’ 和乘法运算符 ’‘ ，这个字符串表示一个 合法 的只含有 个位数数字 的数学表达式（比方说 3+52）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：
按照 从左到右 的顺序计算 乘法 ，然后
按照 从左到右 的顺序计算 加法 。
给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分：
如果一位学生的答案 等于 表达式的正确结果，这位学生将得到 5 分。
否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
否则，这位学生将得到 0 分。
返回所有学生的分数和。
区间型DP
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
class Solution {
public int scoreOfStudents(String s, int[] a) {
// 计算正确答案
int correct = 0;
int n = s.length();
Deque<String> stack = new LinkedList();
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '*') {
int t = Integer.parseInt(stack.pollLast());
stack.offerLast(String.valueOf(t * (s.charAt(++i) - '0')));
} else if (s.charAt(i) != '+') {
stack.offerLast(String.valueOf(s.charAt(i)));
}
}
while (!stack.isEmpty()) {
correct += Integer.parseInt(stack.pollLast());
}
// 区间DP
int[] numbers = new int[(n + 1) / 2];
boolean[] operations = new boolean[n / 2];
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '+') {
operations[i / 2] = true;
} else if (c != '*') {
numbers[i / 2] = c - '0';
}
}
int len = (n + 1) / 2;
Set<Integer>[][] dp = new HashSet[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = new HashSet();
dp[i][i].add(numbers[i]);
}
for (int j = 1; j < len; j++) {
for (int i = j - 1; i >= 0; i--) {
dp[i][j] = new HashSet();
for (int k = i; k < j; k++) {
if (operations[k]) {
for (int x : dp[i][k]) {
for (int y : dp[k + 1][j]) {
if (x + y <= 1000) dp[i][j].add(x + y);
}
}
} else {
for (int x : dp[i][k]) {
for (int y : dp[k + 1][j]) {
if (x * y <= 1000) dp[i][j].add(x * y);
}
}
}
}
}
}
// 统计学生
int res = 0;
for (int x : a) {
if (x == correct) res += 5;
else if (dp[0][len - 1].contains(x)) res += 2;
}
return res;
}
}