Dynamic Programming Exercises Beginner 归档题解(2)

#DP #归档 #总结
Published on 2016-02-13

归档地址
再来10题！

题目

UVa 10817 - Headmaster's Headache

由于每个申请者可选可不选，所以就像一个 01 背包一样。用上一篇定状态的方法，对后面决策的影响就只有现在剩余哪些课没人教。所以定义状态：dp[i][s]dp[i][s] 决策前 i 个老师，剩余未教集合为 s 的最小工资，答案就是 dp[m+n][0]dp[m + n][0]。转移方程很好给出（仔细想一想为什么要并集）：

dp[i][s]=min(dp[i−1][s],dp[i][s∪canTeachi]+salaryi)dp[i][s] = \min(dp[i - 1][s], dp[i][s \cup \text{canTeach}_i] + \text{salary}_i)

然后就是压状态，我是每一门课程压两位，偶数位和紧随其后的奇数位表示一门课程，关键在于用位运算来求并集，优化常数，因为有一门课程两个位，所以比较麻烦。
如果一名老师能教课程 ii，那么二进制第 ii 位设为 11。对于未教集合 SS 与老师能教的课程集合 jj，先按位或 S′=S∣jS' = S \mid j，然后找出那些同为 11 的地方 remain=j−(S′−S)remain = j - (S' - S)，然后将 remainremain 二进制右移一位，这是因为尝试跟某一课程的第一位或失败了，再尝试与课程的第二位或（明白刚才为什么要把同一门课程压在附近了吗）。最后答案就是 S′∣(remain<<1)S' \mid (remain << 1)。
由于在职老师必须选，那么让他们的工资为 00，最后加上他们的工资即可。

UVa 1292 - Strategic game

只能说刘汝佳的翻译又是错的，明明是选最少的点，使每一条边的端点必须有一个节点被选中。根本不是选最少的点，对于没有选中的点，至少有一个相邻的点被选中，这样就不好做了。
这是最小点覆盖的树上版本，先建好树，状态定义 dp[i][j]dp[i][j] 为使以 ii 为根的子树满足条件最少要选多少点，jj 表示 ii 的父亲是否被选。
给出方程：

可以边建树边算，不过这样的话记得要上记忆化。

UVa 1351 - String Compression

题解及代码见 UVa 1351 - String Compression。

UVa 1291 - Dance Dance Revolution

判断相对方向写错，调了很久。。。这是个简单题，用 dp[i][l][r]dp[i][l][r] 表示将要跳 ii，左右脚分别在 l,rl, r 跳完用的最少能量。由于每次只需要移动一个脚（不然花费更大，而且题目也没说允许），决策很好做。

答案是 dp[0][0][0]dp[0][0][0]，考虑到大量废状态（状态中一定有一只脚在上一步的正确位置），使用记忆化递归实现。

UVa 1252 - Twenty Questions

刘汝佳入门经典例题 9-16，这里不再废话解法。但有几点值得注意：

  • cnt[s][a]cnt[s][a] 为满足 aa 中所有特征且不满足 s−as - a 中所有特征的物体个数，所以对于每个 ss，每个物体只可能满足一个 aa，所以不要枚举 aa，这样会大大缩短预处理时间。
  • 由于我们求的是'通解'，即无论心里想的是什么物体都可以在答案内次询问出解，所以我们在决策的时候要找最优决策，但每个决策考虑最坏的情况！

UVa 10163 - Storage Keepers

由于每个仓库都只由一个人管，一个人可管多个仓库，我们不妨假定每个人都看管连续一个区间，为 DP 创造阶段性。然后进行两次 DP，第一次 DP 求出最大的安全等级，第二次求出在当前安全等级下最小的钱。
第一次 DP：dp[i][j]dp[i][j] 为前 ii 个人看管前 jj 个仓库的最大安全的等级。

dp[i][j]={infj=0max(dp[i−1][j],min(dp[i−1][k],j−kp[i])(0≤k<j))dp[i][j] = \begin{cases}\inf & j = 0\\\max(dp[i - 1][j], \min(dp[i -1][k], \frac{j - k}{p[i]}) (0\le k < j))\end{cases}

记最大安全等级为 LL，第二次 DP：dp[i][j]dp[i][j] 为前 ii 个人看管前 jj 个仓库最大安全等级所用的最少钱。

dp[i][j]={0j=0min(dp[i−1][j],dp[i−1][k]+p[i](0≤k<j,j−kp[i]>=L))dp[i][j] = \begin{cases}0 & j = 0\\\min(dp[i - 1][j], dp[i -1][k] + p[i](0\le k < j, \frac{j - k}{p[i]} >= L))\end{cases}

UVa 10453 - Make Palindrome

分析及代码见：UVa 10453 - Make Palindrome。

UVa 10254 - The Priest Mathematician

题目说了，先把 kk 个盘子放到某一根柱子，再把剩下的 n−kn - k 个移动到目标柱子，再将 kk 个移动到目标柱子，设 f4[x]f_{4}[x] 为四根柱子时移动到目标柱子的最小步数， f3[x]=2x−1f_{3}[x] = 2^{x} - 1 为三根柱子时移动到目标柱子的最小步数哦，依据这个写出方程：

由于 n≤10000n \le 10000，看起来要用高精，但高精度要的时间是很多的，我们必须寻找快一点的方法，于是打表找找规律：

看起来增加是有规律的，所以可以快速递推计算。
本代码采用 bitset 高精，仓促写的，速度无法保证。。

UVa 437 - The Tower of Babylon

刘汝佳入门经典第九章，这里不赘述了。

UVa 442 - Matrix Chain Multiplication

居然是个数据结构题，这一题的表达式有一个特殊性：Expression = Matrix | "(" Expression Expression ")"，就是说一个括号里面不会出现三个矩阵相乘，那就很方便了。建立一个栈，遇到字母入栈，遇到右括号将栈顶两个计算一下并压入（顺便判断是否可行），左括号不用管它。

总结

这十个题目还是有一定思维难度的。UVa 10817 - Headmaster's Headache 和 UVa 1252 - Twenty Questions 两个状压的题尤为突出，选用状态压缩的原因是当前状态对后面的决策影响无法用一两个参数搞定，这时候需要完整的记录状态。而状态压缩通常需要用到位运算的优化，需要临场发挥，这里说几个：
判断原串某几位是否都为 11：构造新串，仅让想判断为 11 的位置为 11，再和原串按位或，如果结果等于原串，说明原串某几位都为 11。（原理：新串是 00 的位置'或'不会改变原串的那一位的结果，但为 11 的位置一旦原串不是 11，将会被改变为 11。）

判断原串某几位是否都为 00：构造新串，仅让想判断为 00 的位置为 00，其余都为 11，再和原串按位与，如果结果等于原串，说明原串某几位都为 00。（原理：新串是 11 的位置'与'不会改变原串的那一位的结果，但为 00 的位置一旦原串不是 00，将会被改变为 00。）

而注意 UVa 1252 - Twenty Questions 是找最坏情况下的最优解，所以是最小的最大值。
UVa 10163 - Storage Keepers：本来想一次 DP 搞定，但是失败了（我觉得还是可行的），但请注意 KISS(Keep It Simple ans Stupid)，考场上在复杂度相同的情况下，尽量写简单易懂的。
UVa 10453 - Make Palindrome：做题没有思路的话就尝试着定状态，写方程。
UVa 10254 - The Priest Mathematician：光写出 DP 有时不够，数学题可能有潜在的规律可循，要打表尝试。
UVa 442 - Matrix Chain Multiplication：利用题目的特殊性，简单的求解问题。

代码

UVa 10817 - Headmaster's Headache

//  Created by Sengxian on 2/8/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10817 01背包 + 状压DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

bool EOL = false;
inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    if(ch == '\n') EOL = true;
    return n;
}

const int maxs = 8, maxm = 20 + 3, maxn = 100 + 3, INF = 0x3f3f3f3f;
int s, m, n, salary[maxm + maxn], dp[2][1 << maxs * 2];
int canTeach[maxm + maxn];

inline int add(int S, int j) {
    int _S = S | j, remain = j - (_S - S), res = _S | (remain << 1);
    return res;
}


//dp[i + 1][s] 决策前 i 个老师，剩余未教集合为 i 的最小工资
//答案为 dp[m + n][0];
int solve() {
    int ALL = (1 << s * 2) - 1;
    memset(dp[0], INF, sizeof(dp[0]));
    dp[0][ALL] = 0;
    for(int i = 0; i < n + m; ++i) {
        int _i = i & 1;
        for(int S = ALL; S >= 0; --S) {
            int new_S = add(S, canTeach[i]);
            dp[!_i][S] = min(dp[_i][S],  dp[_i][new_S] + salary[i]);
        }
    }
    return dp[(n + m) & 1][0];
}

int Read() {
    int s = 0;
    EOL = false;
    while(!EOL) s += 1 << (ReadInt() - 1) * 2;
    return s;
}

int main() {
    while(s = ReadInt(), m = ReadInt(), n = ReadInt(), s) {
        int tot = 0;
        for(int i = 0; i < m; ++i) {
            tot += ReadInt();
            salary[i] = 0;
            canTeach[i] = Read();
        }
        for(int i = 0; i < n; ++i) {
            salary[i + m] = ReadInt();
            canTeach[i + m] = Read();
        }
        printf("%d\n", solve() + tot);
    }
    return 0;
}

UVa 1292 - Strategic game

//  Created by Sengxian on 2/8/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1292 树形 DP(最小点覆盖)
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}
const int maxn = 1500 + 3, INF = 0x3f3f3f3f;
vector<int> G[maxn];
int n;
int mem[maxn][2];

int dp(int u, bool choose, int fa) {
    if(mem[u][choose] != -1) return mem[u][choose];
    int a1 = 1, a2 = INF;
    for(int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if(v != fa) a1 += dp(v, true, u);
    }
    if(choose || fa == -1) {
        a2 = 0;
        for(int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if(v != fa) a2 += dp(v, false, u);
        }
    }
    return mem[u][choose] = min(a1, a2);
}

int main() {
    while(~scanf("%d", &n) && n) {
        for(int i = 0; i < n; ++i) G[i].clear(), mem[i][0] = mem[i][1] = -1;
        for(int i = 0; i < n; ++i) {
            int f = ReadInt(), x = ReadInt(), t;
            while(x--) t = ReadInt(), G[f].push_back(t), G[t].push_back(f);
        }
        printf("%d\n", dp(0, 0, -1));
    }
    return 0;
}

UVa 1291 - Dance Dance Revolution

//  Created by Sengxian on 2/9/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1291 跳舞机上的DP(easy)
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 10000 + 3, INF = 0x3f3f3f3f;
int seq[maxn], n, dp[maxn][5][5];
//0 - central 1 - top 2 - left 3 - bottom 4 - right

inline int energy(int f, int t) {
    if(f == t) return 1; //don't move
    if(f == 0) return 2; //from central
    if((f + t == 6) || (f + t) == 4) return 4; //oppoite
    return 3; //adajcent
} 

int solve(int cur, int left, int right) {
    if(cur == n) return 0;
    if(dp[cur][left][right] != -1) return dp[cur][left][right];
    int &ans = dp[cur][left][right] = INF;
    //move left foot correct
    if(seq[cur] != right)
        ans = min(ans, solve(cur + 1, seq[cur], right) + energy(left, seq[cur]));
    //move right foot correct
    if(seq[cur] != left)
        ans = min(ans, solve(cur + 1, left, seq[cur]) + energy(right, seq[cur]));
    return ans;
}

int main() {
    while(seq[0] = ReadInt(), seq[0]) {
        n = 1;
        while(seq[n] = ReadInt(), seq[n]) n++;
        assert(n < maxn);
        for(int i = 0; i < n; ++i) memset(dp[i], -1, sizeof(dp[i]));
        printf("%d\n", solve(0, 0, 0));
    }
    return 0;
}

UVa 1252 - Twenty Questions

//  Created by Sengxian on 2/9/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1252 状压dp + 预处理
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 128 + 3, maxm = 11 + 0;
int m, n, objs[maxn], cnt[1 << maxm][1 << maxm], dp[1 << maxm][1 << maxm];
char str[maxm];

//计算 cnt[s][a] 满足 a 中所有且不满足 s - a 中所有的个数
void process() {
    for(int s = 0; s < 1 << m; ++s) {
        fill(cnt[s], cnt[s] + s + 1, 0);
        fill(dp[s], dp[s] + s + 1, -1);
        for(int i = 0; i < n; ++i)
            cnt[s][objs[i] & s]++; //显而易见，对于每个 s，每个 obj 只可能满足一个 a，所以不要枚举 a！
    }
}

int solve(int s, int a) {
    if(cnt[s][a] == 0 || cnt[s][a] == 1) return 0;
    if(dp[s][a] != -1) return dp[s][a];
    int &ans = dp[s][a] = INT_MAX;
    for(int i = 0; i < m; ++i)
        if(((s >> i) & 1) == 0) //找最优决策，但每个决策考虑最坏的情况！
            ans = min(ans, max(solve(s + (1 << i), a), solve(s + (1 << i), a + (1 << i))) + 1);
    return ans;
}

int main() {
    while(m = ReadInt(), n = ReadInt(), m + n) {
        for(int i = 0; i < n; ++i) {
            objs[i] = 0; scanf("%s", str);
            for(int j = 0; j < m; ++j)
                objs[i] += (str[j] - '0') << j;
        }
        process();
        printf("%d\n", solve(0, 0));
    }        
    return 0;
}

UVa 10163 - Storage Keepers

//  Created by Sengxian on 2/9/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10163 两次 DP
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxm = 100 + 3, maxn = 30 + 3;
int n, m, p[maxm];

const int INF = 0x3f3f3f3f;
int dp[maxn][maxm]; //dp[i][j] 前 i 个人看守前 j 个仓库的最大安保等级

int solve() {
    dp[0][0] = INF;
    for(int i = 1; i <= m; ++i) dp[0][i] = -INF; 
    for(int i = 1; i <= n; ++i) {
        dp[i][0] = INF;
        for(int j = 1; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j];
            for(int k = 0; k < j; ++k) {
                dp[i][j] = max(dp[i][j], min(dp[i - 1][k], p[i] / (j - k)));
            }
        }
    }
    int l = dp[n][m];
    printf("%d ", dp[n][m]);
    if(dp[n][m]) {
        dp[0][0] = 0;
        for(int i = 1; i <= m; ++i) dp[0][i] = INF;
        for(int i = 1; i <= n; ++i) {
            dp[i][0] = 0;
            for(int j = 1; j <= m; ++j) {
                dp[i][j] = dp[i - 1][j];
                for(int k = j - 1; k >= 0 && p[i] / (j - k) >= l; --k)
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + p[i]);
            }
        }
        printf("%d\n", dp[n][m]);
    }else printf("0\n");
}

int main() {
    while(m = ReadInt(), n = ReadInt(), n + m) {
        for(int i = 1; i <= n; ++i)
            p[i] = ReadInt();
        solve();
    }    
    return 0;
}

UVa 10254 - The Priest Mathematician

//  Created by Sengxian on 2/10/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10254 递推＋打表＋高精度
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <bitset>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch) && ch != EOF) ch = getchar();
    if(ch == EOF) return -1;
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 10000 + 3;
inline ll f3(int x) {
    return (1LL << x) - 1;
}

typedef struct{
    int len;
    char value[100];
} TBigInt, *pBigInt;

void AddBit(pBigInt s, char BitValue) {
    for(int i = 0; i < s -> len; ++i)
        s -> value[i] *= 2; 
    s -> value[0] += BitValue;
    for(int i = 0; i < s -> len; ++i) {
        s -> value[i + 1] += s -> value[i] / 10;
        s -> value[i] %= 10;
    }
    if(s -> value[s -> len]) s -> len++;
}

void OutputBigInt(pBigInt s){
    if (s -> len == 0) putchar('0');
    else for (int i = s -> len - 1; i >= 0; i--) putchar(s -> value[i] + '0');
}


struct BigInt {
    static const int maxLen = 300;
    bitset<maxLen> b;
    void init() { b.reset(); }
    BigInt() { b.reset(); }    
    BigInt operator = (ll val) {
        int x = 0;
        b.reset();
        while(val) {
            if(val & 1) b[x] = 1;
            x++; val >>= 1;
        }
        return *this;
    }
    BigInt(ll val) { *this = val; }
    BigInt operator = (const BigInt &a) { b = a.b; return *this; }
    BigInt operator + (BigInt a) const {
        BigInt ret = *this; bitset<maxLen> add;
        while(a.b.count()) {
            add = a.b & ret.b;
            add <<= 1;
            ret.b ^= a.b;
            a.b = add;
        }
        return ret;
    }
    BigInt operator * (ll val) const {
        BigInt ret = *this;
        int x = 0;
        while(val) {
            if(val & 1) ret.b <<= 1;
            x++; val >>= 1;
        }
        return ret;
    }
    void print() const {
        static TBigInt BigInt;
        memset(&BigInt,0, sizeof BigInt);
        int i = maxLen - 1;
        while(i >= 1 && !b[i]) i--;
        for (; i >= 0; --i) AddBit(&BigInt, b[i]);
        OutputBigInt(&BigInt);
    }
    bool operator < (const BigInt &a) const {    
        for(int i = maxLen - 1; i >= 0; --i)
            if(b[i] != a.b[i]) return b[i] < a.b[i];
        return false;
    }
    void printLine() {
        print(); br
    }
};



BigInt f4[maxn];

int main() {
    BigInt add = 2;
    int k = 1, cnt = 0;
    f4[1] = 1; f4[0] = 0;
    for(int i = 2; i < maxn; ++i) {
        f4[i] = f4[i - 1] + add;
        cnt++;
        if(cnt == k + 1) {
            cnt = 0;
            k++;
            add = add + add;
        }
    }
    int x;
    while(x = ReadInt(), ~x) f4[x].printLine();
    return 0;
}

UVa 437 - The Tower of Babylon

//  Created by Sengxian on 15/10/9.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 35, INF = 100000000;
int tower[maxn][3], n;

bool canPlace(int l, int h, int l1, int h1) {
    return (l > l1 & h > h1) | (l > h1 & h > l1);
}

void getHL(int idx, int k, int &h, int &l) {
    if(k == 0) {
        h = tower[idx][1]; l = tower[idx][2];
    }else if(k == 1) {
        h = tower[idx][0]; l = tower[idx][2];
    }else {
        h = tower[idx][0]; l = tower[idx][1];
    }
}

int dp[maxn][3];

int MaxHeight(int idx, int k) {
    if(dp[idx][k] != -1) return dp[idx][k];
    int h, l;

    getHL(idx, k, h, l);

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        //决策高
        for(int j = 0; j < 3; ++j) {
            int h1, l1;

            getHL(i, j, h1, l1);
            if(canPlace(h, l, h1, l1)) ans = max(ans, MaxHeight(i, j) + tower[i][j]);
        }
    }
    return dp[idx][k] = ans;
}

int main() {
    int caseNum = 0;
    tower[0][0] = INF, tower[0][1] = INF, tower[0][2] = 0;
    while(scanf("%d", &n) != EOF && n) {
        for(int i = 1; i <= n; ++i)
            cin >> tower[i][0] >> tower[i][1] >> tower[i][2];
            memset(dp, -1, sizeof(dp));
            printf("Case %d: maximum height = %d\n", ++caseNum, MaxHeight(0, 2));
    }
    return 0;
}

UVa 442 - Matrix Chain Multiplication

//  Created by Sengxian on 2/13/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 442 表达式（栈）
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

inline char ReadAlpha() {
    char ch = getchar();
    while(!isalpha(ch)) ch = getchar();
    return ch;
}
const int maxn = 26;
struct Matrix {
    int a, b;
    Matrix(int a = 0, int b = 0): a(a), b(b) {}
}ms[maxn];
string expression;
int n;

int cal() {
    int res = 0;
    stack<Matrix> stk;
    for(int i = 0; i < expression.length(); ++i) {
        if(isalpha(expression[i])) stk.push(ms[expression[i] - 'A']);
        else if(expression[i] == ')') {
            Matrix m2 = stk.top(); stk.pop();
            Matrix m1 = stk.top(); stk.pop();
            if(m1.b != m2.a) return -1;
            res += m1.a * m1.b * m2.b;
            stk.push(Matrix(m1.a, m2.b));
        }
    }
    return res;
}

int main() {
    n = ReadInt();
    for(int i = 0; i < n; ++i) {
        int idx = ReadAlpha() - 'A';
        ms[idx].a = ReadInt(), ms[idx].b = ReadInt();
    }
    while(cin >> expression) {
        int res = cal();
        if(res >= 0) printf("%d\n", res);
        else puts("error");
    }
    return 0;
}
Dynamic Programming Exercises Beginner 归档题解(3)