Dynamic Programming Exercises Beginner 归档题解(1)

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

归档地址

搞这个归档模块，其实是我想写题解却懒得搞题意和输入输出之类的，这样可以方便我写分析。所以题意大家就看刘汝佳的训练指南 P93 吧。再一个是我 DP 弱的要死，赶紧总结一下方法。。。

本题解是边做题边写的，所以比较仓促，有问题欢迎留言，或是发我邮件 sengxian at live.com

题目

UVa 11584 - Partitioning by Palindromes

预处理出 ii 到 jj 是不是回文串，来一个简单的 dp 就行了。注意奇偶两种回文串。

UVa 1424 - Salesmen

如果认为当前状态可能对后面有影响，使当前状态最优却不一定使后面的状态更优的时候，分析状态的哪些因素可能对后面有影响，然后把这些因素加入状态。本题中是序列的最后一个数可能对后面有影响，于是我们把序列的最后一个数加入状态定义。
决策优化。下一层只考虑本层成立的状态。

UVa 10534 - Wavio Sequence

找最长波浪子序列，正反各一次找 LIS 即可。要理解 LIS 的 O(nlogn)O(n\log n) 算法的本质是用单调队列优化了决策，实际上并没有破坏原来的定义（d[i]d[i] 是以 ii 结尾的最长上升子序列的长度）。

UVa 11552 - Fewest Flops

跟第一题一样，如果认为当前状态对后面有影响，那么就把可能造成影响的因素加入状态定义。这里也是最后一个字母可能有影响，而且块是天然的序，所以我们这样定状态：

dp[i][j]dp[i][j]：处理完前 ii 个块，最后一个字符是 j 的最小块数。

每一个块一样的字符肯定排在一起，再考虑特殊情况，不难得出转移方程（kinds\mathrm{kinds} 是第 ii 个块内字符种类数）：

注意 k=jk = j 的时候如果不是块里面全为 jj，是减不掉这个 11 的。

UVa 11404 - Palindromic Subsequence

这一题一看没什么思路，看了看刘汝佳给的一句话提示：可以转化为 LCS，恍然大悟。

首先回文串有两种，奇回文和偶回文，但无论哪一种，后一半是前一半的逆转。所以我们把原串翻转，求取原串和翻转串的 LCS，然后逐位枚举回文串的中心，奇回文的中心就是一个，偶数回文的中心有一前一后两个，找到中心在逆序串中的位置求取 LCS 可得长度。

串怎么求？还是字典序最小的？好办，再记录一个 mem[i][j]mem[i][j] 表示原串前 ii 个字符与翻转串前 jj 个字符构成的最长且最小字典序的 LCS 。那么 dp 时只有在相等的情况下才从 mem[i−1][j−1]mem[i - 1][j - 1] 追加一个字符，其余情况取最长且字典序最小的即可。加上内存池优化，这个能跑 0.312s。

当然还有更快的办法（麻烦一点，不看也罢），因为我们找 LCS 的时候在原串里面确定一个位置，在翻转串中只会找对应的位置，所以大量状态可能用不到！所以另一个思路是 dp 时不存字符串，要的时候再记忆化递归去找。这样大概能跑 0.242s。

UVa 1456 - Cellular Network

题意看懂大概就不难，假如我们让每一组都是连续的话，那么一定是概率从大到小排序才划算，因为越到后面乘的系数越大。

设 dp[i][j]dp[i][j] 为将前 ii 个分为 jj 组，最小的数学期望。方程很容易搞出来：

UVa 11795 - Mega Man's Mission

稍微有一点点思维，读入武器的时候直接压成二进制位，第 ii 位（从 00开始）表示此武器能否消灭第 ii 个敌人。接着使用状压 DP：

dp[s]dp[s] 表示剩余敌人的集合为 ss，消灭他们有多少种不同的顺序。计算的时候先处理出能够打的敌人集合 cancan，计算方法是将所有已经消灭的敌人的武器的的集合和初始武器 '或' 起来，这样常数就很小。

dp[s]=∑i∈cani∈sdp[s\{i}]\displaystyle dp[s] = \sum\limits_{i \in can\,i \in s}dp[s \backslash \{i\}]

考虑到有一些状态可能不会访问到，所以使用记忆化递归实现。

UVa 1452 - Jump

分析与代码见 UVa 1452 - Jump。

UVa 1366 - Martian Mining

首先要知道，每个格子肯定都要挖，之前被图例困扰了很久，以为有什么特殊限制。。。

那么就很好搞 DP 了，由于 A、B 矿全部都是直线而且要么向左要么向上，所以可以对 A 处理出每一行的前缀和，对 B 处理出每一列的前缀和，由于在某一点选了 A 矿就必定会选同一行之前的所有，而某一点选了 B 矿就必定会选同一列之前的所有。定义 dp[i][j]dp[i][j] 为前 ii 行前 jj 列的最大收益，那么方程不难列出：

可用数学归纳法证明这样的状态表示以及决策可以包括所有的状态！网上三维的状态明显复杂了。

UVa 10564 - Paths through the Hourglass

我认为这题难点在于标号23333。先写一个函数计算第 ii 行有多少个数方便计算，然后每一行不管有几个数都从 00 开始标号，对于沙漏上边（不含只有一个数的那一行）某一行标号 jj，走左是下一行的标号 j−1j - 1，走右是下一行的标号 jj。对于下方某一行标号 jj，走左是下一行的标号 jj，走右是下一行的标号 j+1j + 1。

由于 SS 不大，剩下的就是普通 dp，dp[i][j][s]dp[i][j][s] 表示 ii 行，标号 jj，目前和（包括自己这一格子）的和为 ss 的方案总数，然后方程是：

注意一下边界就行。本题还要求最小字典序，故采用记忆化递归实现，第一个到达终点且可行的记录一下即可。

总结

前 10 题还是不错的，有经典问题的规约（需完全理解经典问题），也不乏思维题，总结方法最重要。深刻领悟了定状态的方法：“如果认为当前状态可能对后面有影响，使当前状态最优却不一定使后面的状态更优的时候，分析状态的哪些因素可能对后面有影响，然后把这些因素加入状态定义。”

代码

UVa 11584 - Partitioning by Palindromes

//  Created by Sengxian on 15/10/10.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1005, INF = 1000000000;
char str[maxn];
bool isP[maxn][maxn]; //isP[i][j] i - j 是不是一个回文串
int d[maxn], n; //0 - i的最小回文分解

int main() {
    int T;
    cin >> T;
    d[0] = 0;
    while(T--) {
        memset(isP, 0, sizeof(isP));
        scanf("%s", str + 1);
        n = strlen(str + 1);
        //回文串预处理
        for(int i = 1; i <= n; ++i) {
            int p = i, q = i; //长度为奇数的回文判断
            while(p > 0 && q <= n && str[p] == str[q]) {
                isP[p][q] = true;
                isP[q][p] = true;
                p--; q++;
            }
            p = i, q = i + 1; //长度为偶数的回文判断
            while(p > 0 && q <= n && str[p] == str[q]) {
                isP[p][q] = true;
                isP[q][p] = true;
                p--; q++;
            }
        }

        for(int i = 1; i <= n; ++i) {
            d[i] = INF;
            for(int j = 1; j <= i; ++j)
                if(isP[j][i])
                    d[i] = min(d[i], d[j - 1] + 1);
        }

        printf("%d\n", d[n]);
    }
    return 0;
}

UVa 1424 - Salesmen

//  Created by Sengxian on 2/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1424 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 = 100 + 3, maxl = 200 + 3, INF = 0x3f3f3f3f;
bool G[maxn][maxn];
int n, m, l, a[maxl], dp[maxl][maxn], s[maxn];

int Solve() {
    fill(dp[0], dp[0] + n, 0);
    int cnt = n;
    for(int i = 0; i < n; ++i) s[i] = i;
    for(int i = 0; i < l; ++i) {
        for(int j = 0; j < n; ++j) {
            dp[i + 1][j] = INF;
            for(int _k = 0; _k < cnt; ++_k) {
                int k = s[_k];
                if(G[j][k] == true || j == k) dp[i + 1][j] = min(dp[i + 1][j], dp[i][k]);
            }
            if(j != a[i]) dp[i + 1][j]++;
        }
        cnt = 0; //决策优化，下一层只考虑本层成立的状态
        for(int j = 0; j < n; ++j) if(dp[i + 1][j] < INF) s[cnt++] = j;
    }
    return *min_element(dp[l], dp[l] + n);
}

int main() {
    int caseNum = ReadInt(), f, t;
    while(caseNum--) {
        n = ReadInt(), m = ReadInt();
        for(int i = 0; i < n; ++i) fill(G[i], G[i] + n, false);
        for(int i = 0; i < m; ++i) {
            f = ReadInt() - 1, t = ReadInt() - 1;
            G[t][f] = G[f][t] = true;
        }
        l = ReadInt();
        for(int i = 0; i < l; ++i)
            a[i] = ReadInt() - 1;
        printf("%d\n", Solve());
    }    
    return 0;
}

UVa 10534 - Wavio Sequence

//  Created by Sengxian on 2/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10534 LIS
#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 != EOF) ch = getchar();
    if(ch == EOF) return 0;
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 10000 + 3;
int n, a[maxn], decrease[maxn], increase[maxn], g[maxn];

int main() {
    while(n = ReadInt(), n) {
        for(int i = 0; i < n; ++i) a[i] = ReadInt();
        memset(g, 0x3f, sizeof(int) * n);
        for(int i = 0; i < n; ++i) {
            int k = lower_bound(g, g + n, a[i]) - g;
            increase[i] = k + 1;
            g[k] = a[i];
        }
        memset(g, 0x3f, sizeof(int) * n);
        for(int i = n - 1; i >= 0; --i) {
            int k = lower_bound(g, g + n, a[i]) - g;
            decrease[i] = k + 1;
            g[k] = a[i];
        }
        int ans = 0;
        for(int i = 0; i < n; ++i) ans = max(ans, min(increase[i], decrease[i]));
        printf("%d\n", ans * 2 - 1);
    }    
    return 0;
}

UVa 11552 - Fewest Flops

//  Created by Sengxian on 2/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11552 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 = 1000 + 3, charNum = 26, INF = 0x3f3f3f3f;
char str[maxn];
int k, n, dp[2][charNum], cnt[charNum], s[charNum];

int Solve() {
    int m = 0;
    n = strlen(str) / k;
    for(int i = 0; i < n; ++i) {
        int kinds = 0, _i = i & 1;
        memset(cnt, 0, sizeof(cnt));
        for(int j = 0; j < k; ++j) cnt[str[i * k + j] - 'a']++;
        for(int j = 0; j < charNum; ++j) kinds += cnt[j] > 0;
        for(int j = 0; j < charNum; ++j) {
            dp[_i][j] = INF;
            if(!cnt[j]) continue;
            if(i == 0) {dp[_i][j] = kinds; continue;}
            for(int __k = 0; __k < m; ++__k) {
                int _k = s[__k];
                dp[_i][j] = min(dp[_i][j], dp[!_i][_k] + kinds - (cnt[_k] > 0 && (_k != j || kinds == 1))); //注意 k = j 的时候如果不是块里面全为 j，是减不掉这个 1 的。
            }
        }
        m = 0; //决策优化
        for(int j = 0; j < charNum; ++j) if(dp[_i][j] < INF) s[m++] = j;
    }
    return *min_element(dp[(n - 1) & 1], dp[(n - 1) & 1] + charNum);
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        k = ReadInt();
        scanf("%s", str);
        printf("%d\n", Solve());
    }
    return 0;
}

UVa 11404 - Palindromic Subsequence

版本一：

//  Created by Sengxian on 2/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11404 转化为 LCS
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <string>
#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 = 1000 + 3;
char str1[maxn], str2[maxn];
int n, dp[maxn][maxn];
string *mem[maxn][maxn], pool[maxn * maxn], *pits;

//type = 0 奇回文，否则是偶回文    
inline string getStr(int i, int j, bool type) {
    string s = *mem[i][j], half;
    if(type == false) half = s.substr(0, s.length() - 1);
    else half = s;
    reverse(half.begin(), half.end());
    return s + half;
}

inline string* getNew() {
    pits -> clear();
    return pits++;
}

void Solve() {
    int ans = 0; string s;
    for(int i = 1; i <= n; ++i) {
        //奇回文
        int now = dp[i][n + 1 - i] * 2 - 1;
        if(now > ans) ans = now, s = getStr(i, n + 1 - i, 0);
        else if(now == ans) {
            string new_s = getStr(i, n + 1 - i, 0);
            if(new_s < s) s = new_s;
        }
        //偶回文
        if(i == n) continue;
        now = dp[i][n - i] * 2;
        if(now > ans) ans = now, s = getStr(i, n - i, 1);
        else if(now == ans) {
            string new_s = getStr(i, n - i, 1);
            if(new_s < s) s = new_s;
        }
    }
    printf("%s\n", s.c_str());
}

int main() {
    while(~scanf("%s", str1 + 1)) {
        n = strlen(str1 + 1);
        for(int i = 1; i <= n; ++i) str2[i] = str1[n + 1 - i];
        pits = pool;
        string *null = getNew();
        for(int i = 0; i <= n; ++i) mem[0][i] = mem[i][0] = null; //初始化
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j) {
                if(str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    mem[i][j] = getNew();
                    *mem[i][j] = *mem[i - 1][j - 1] + str1[i];
                }else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    if(dp[i - 1][j] > dp[i][j - 1]) mem[i][j] = mem[i - 1][j];
                    else if(dp[i - 1][j] < dp[i][j - 1]) mem[i][j] = mem[i][j - 1];
                    else { //这时要看字典序了
                        if(*mem[i - 1][j] < *mem[i][j - 1])
                            mem[i][j] = mem[i - 1][j];
                        else mem[i][j] = mem[i][j - 1];
                    }
                }
            }
        Solve();
    }        
    return 0;
}

版本二：

//  Created by Sengxian on 2/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11404 转化为 LCS
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <string>
#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 = 1000 + 3;
char str1[maxn], str2[maxn];
int n, dp[maxn][maxn], decision[maxn][maxn];
bool vis[maxn][maxn]; string mem[maxn][maxn];

string get(int i, int j) {
    if(i <= 0 || j <= 0) return "";
    if(vis[i][j]) return mem[i][j];
    vis[i][j] = true;
    string &s = mem[i][j];
    s.clear();
    while(i && j) {
        if(decision[i][j] == 1) {
            s += str1[i];
            i--; j--;
        }else if(decision[i][j] == 2) i--;
        else if(decision[i][j] == 3) j--;
        else { //进入分叉，递归下去取反向字典序更小的那个
            string a1 = get(i, j - 1), a2 = get(i - 1, j);
            reverse(a1.begin(), a1.end());
            reverse(a2.begin(), a2.end());
            if(a1 < a2) {
                reverse(a1.begin(), a1.end());
                s += a1;
            }else reverse(a2.begin(), a2.end()), s += a2;
            break;    
        }
    }
    return s;
}

//type = 0 奇回文，否则是偶回文    
inline string getStr(int i, int j, bool type) {
    string s = get(i, j), half;
    reverse(s.begin(), s.end());
    if(type == false) half = s.substr(0, s.length() - 1);
    else half = s;
    reverse(half.begin(), half.end());
    return s + half;
}

int main() {
    while(~scanf("%s", str1 + 1)) {
        n = strlen(str1 + 1);
        for(int i = 1; i <= n; ++i) str2[i] = str1[n + 1 - i];
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    decision[i][j] = 1; //相等
                }else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                    if(dp[i - 1][j] > dp[i][j - 1]) decision[i][j] = 2;
                    else if(dp[i - 1][j] < dp[i][j - 1]) decision[i][j] = 3;
                    else decision[i][j] = 4; //这时要看字典序了
                }
        memset(vis, 0, sizeof(vis));
        int ans = 0; string s;
        for(int i = 1; i <= n; ++i) {
            //奇回文
            int now = dp[i][n + 1 - i] * 2 - 1;
            if(now > ans) ans = now, s = getStr(i, n + 1 - i, 0);
            else if(now == ans) {
                string new_s = getStr(i, n + 1 - i, 0);
                if(new_s < s) s = new_s;
            }
            //偶回文
            if(i == n) continue;
            now = dp[i][n - i] * 2;
            if(now > ans) ans = now, s = getStr(i, n - i, 1);
            else if(now == ans) {
                string new_s = getStr(i, n - i, 1);
                if(new_s < s) s = new_s;
            }
        }    
        printf("%s\n", s.c_str());
    }        
    return 0;
}

UVa 1456 - Cellular Network

//  Created by Sengxian on 2/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1456 贪心 + 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 = 100 + 3, maxw = 100 + 3, INF = 0x3f3f3f3f;
int n, w, u[maxn];
double c[maxn], dp[maxn][maxw];

double solve() {
    fill(dp[0], dp[0] + w + 1, INF);
    dp[0][0] = 0;
    for(int i = 1; i <= n; ++i) { 
        fill(dp[i], dp[i] + n + 1, INF); //dp[i][0] = INF 除非 i = 0，否则一定不合法！
        for(int j = 1; j <= w; ++j) {
            for(int k = 1; k <= i; ++k)
                dp[i][j] = min(dp[i][j], i * (c[i] - c[k - 1]) + dp[k - 1][j - 1]);
        }
    }
    return dp[n][w];
}

bool cmp(double a, double b) {
    return a > b;
}

int main() {
    int caseNum = ReadInt();
    while(caseNum--) {
        n = ReadInt(), w = ReadInt();
        int sum = 0;
        for(int i = 1; i <= n; ++i) sum += u[i] = ReadInt();
        for(int i = 1; i <= n; ++i) c[i] = (double)u[i] / sum;
        sort(c + 1, c + 1 + n, cmp);
        for(int i = 2; i <= n; ++i) c[i] += c[i - 1];
        printf("%.4lf\n", solve());
    }
    return 0;
}

UVa 11795 - Mega Man's Mission

//  Created by Sengxian on 2/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11795 状压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 = 16 + 1;
typedef long long ll;
int n, megabuster, weapons[maxn];
ll mem[1 << maxn];

ll dp(int S) {
    if(S == 0) return 1;
    if(mem[S] != -1) return mem[S];
    ll &cnt = mem[S] = 0;
    int can = megabuster;
    for(int i = 0; i < n; ++i)
        if(((S >> i) & 1) == 0) can |= weapons[i];
    for(int i = 0; i < n; ++i)
        if((S >> i) & 1 && (can >> i) & 1)
            cnt += dp(S ^ (1 << i));
    return cnt;
}

char str[maxn];

int main() {
    int caseNum = ReadInt();
    for(int t = 1; t <= caseNum; ++t) {
        n = ReadInt();
        megabuster = 0; scanf("%s", str);
        for(int i = 0; i < n; ++i)
            megabuster += (str[i] - '0') << i;
        for(int i = 0; i < n; ++i) {
            weapons[i] = 0; scanf("%s", str);
            for(int j = 0; j < n; ++j) weapons[i] += (str[j] - '0') << j;
        }
        memset(mem, -1, sizeof(ll) * (1 << n));
        printf("Case %d: %lld\n", t, dp((1 << n) - 1));
    }    
    return 0;
}

UVa 1366 - Martian Mining

//  Created by Sengxian on 2/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1366 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 = 500 + 3, maxm = 500 + 3;
int a[maxn][maxm], suma[maxn][maxm], b[maxn][maxm], sumb[maxm][maxn], n, m;
int dp[maxn][maxm];

int solve() {
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            dp[i][j] = max(dp[i - 1][j] + suma[i][j], dp[i][j - 1] + sumb[j][i]);
    return dp[n][m];
}

int main() {
    while(n = ReadInt(), m = ReadInt(), n + m) {
        for(int i = 1; i <= n; ++i) {
            suma[i][0] = 0;
            for(int j = 1; j <= m; ++j)
                suma[i][j] = (a[i][j] = ReadInt()) + suma[i][j - 1];
        }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                b[i][j] = ReadInt();
        for(int j = 1; j <= m; ++j) {
            sumb[j][0] = 0;
            for(int i = 1; i <= n; ++i)
                sumb[j][i] = b[i][j] + sumb[j][i - 1];
        }
        printf("%d\n", solve());
    }
    return 0;
}

UVa 10564 - Paths through the Hourglass

//  Created by Sengxian on 2/7/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 10564 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 = 20 + 3, maxSum = 500 + 3;
int n, s, a[maxn * 2][maxn];
bool flag, opers[maxn * 2], ansOpers[maxn * 2];
typedef long long ll;
ll mem[maxn * 2][maxn][maxSum];

inline int getNum(int line) {
    if(line < n - 1) return n - line;
    else return 2 + line - n;
}

inline bool check(int i, int j) {
    return j >= 0 && j < getNum(i);
}

ll dp(int i, int j, int _s) {
    if(i == 2 * n - 2) {
        if(_s == s && !flag) {
            flag = true;
            memcpy(ansOpers, opers, sizeof(opers));
        }
        return _s == s; 
    }
    if(mem[i][j][_s] != -1) return mem[i][j][_s];
    ll &cnt = mem[i][j][_s] = 0;
    if(i < n - 1) {
        for(int k = j - 1; k <= j; ++k)
            if(check(i + 1, k)) {
                opers[i] = k == j - 1 ? 0 : 1;
                cnt += dp(i + 1, k, _s + a[i + 1][k]);
            }
    }else {
        for(int k = j; k <= j + 1; ++k)
            if(check(i + 1, k)) {
                opers[i] = k == j ? 0 : 1;
                cnt += dp(i + 1, k, _s + a[i + 1][k]);
            }
    }
    return cnt;
}

int main() {
    while(n = ReadInt(), s = ReadInt(), n + s) {
        for(int i = 0; i < n * 2 - 1; ++i) {
            for(int j = 0, l = getNum(i); j < l; ++j)
                a[i][j] = ReadInt();
        }
        memset(mem, -1, sizeof(mem));
        flag = false;
        ll cnt = 0; int rec = -1;
        for(int i = 0; i < n; ++i) {
            cnt += dp(0, i, a[0][i]);
            if(rec == -1 && flag) rec = i;
        }
        printf("%lld\n", cnt);
        if(cnt) {
            printf("%d ", rec);
            for(int i = 0; i < 2 * n - 2; ++i)
                putchar(ansOpers[i] ? 'R' : 'L');
            br
        }else br
    }
    return 0;
}
UVa 1452 - Jump