解題區►解題區 - UVa

UVa 11724 - Evaluate the Expression

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每個變數皆為正整數，給定一個算術表達式和變數之間的大小關係，請問最少產生出來的答案為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0

Sample Output

1
2
3
Case 1: 4
Case 2: 9
Case 3: 4

Solution

先使用 spfa 找到根據 greedy 策略分配的變數值，如果發生負環情況直接輸出 -1。

然後使用矩陣鏈乘積的 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
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
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
char exp[1024], cond[1024];
int val[26];
int spfa(vector<int> g[]) {
	queue<int> Q;
	int inq[26] = {}, dist[26] = {};
	int cnt[26] = {};
	int u, v;
	for (int i = 0; i < 26; i++) {
		Q.push(i), dist[i] = 1;
	}
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		inq[u] = 0;
		for (int i = 0; i < g[u].size(); i++) {
			v = g[u][i];
			if (dist[v] < dist[u] + 1) {
				dist[v] = dist[u] + 1;
				if (!inq[v]) {
					inq[v] = 1, Q.push(v);
					if (++cnt[v] > 26)
						return 0;
				}
			}
		}
	}
	for (int i = 0; i < 26; i++)
		val[i] = dist[i];
	return 1;
}
int used[512][512];
long long dp[512][512];
long long dfs(int l, int r) {
	if (used[l][r])
		return dp[l][r];
	if (l == r)
		return val[exp[l] - 'a'];
	used[l][r] = 1;
	long long &ret = dp[l][r];
	ret = 1LL<<60;
	int p = 0, test = 0;
	for (int i = l; i <= r; i++) {
		if (exp[i] == '(')	p++;
		if (exp[i] == ')')	p--;
		if (p == 0 && exp[i] == '+') {
			ret = min(ret, dfs(l, i-1) + dfs(i+1, r));
			test++;
		}
		if (p == 0 && exp[i] == '*') {
			ret = min(ret, dfs(l, i-1) * dfs(i+1, r));
			test++;
		}
	}
	if (test == 0)
		ret = min(ret, dfs(l+1, r-1));
	return ret;
}
int main() {
	int testcase, cases = 0;
	int n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%s", exp);
		scanf("%d", &n);
		vector<int> g[26];
		for (int i = 0; i < n; i++) {
			scanf("%s", cond);
			g[cond[2]-'a'].push_back(cond[0]-'a');
		}
		printf("Case %d: ", ++cases);
		if(!spfa(g)) {
			puts("-1");
		} else {
			memset(used, 0, sizeof(used));
			printf("%lld\n", dfs(0, strlen(exp) - 1));
		}
	}
	return 0;
}
/*
3
a+b*c
2
a>b
c>b
z*(x+y)
3
z>x
x>y
z>y
a+b+c+a
0
*/