阿里 4.7 第二题不会

第一题

就是a+b problem
只不过他输入的是字符串
用)!@#$%^&*(来表示0123456789
负号仍然用-
输入两个字符串表示两个数，然后输出a+b、a-b和b-a
C++要开long long，java要开long
没啥技术含量

#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
int main() {
    char ch[] = ")!@#$%^&*(";
    map<char, int> mp1;
    map<int, char> mp2;
    for(int i = 0; i < 10; ++i) {
        mp1[ch[i]] = i;
        mp2[i] = ch[i];
    }

    auto toNum = [&mp1](char* s) {
        long long k = 1, x = 0;
        if(s[0] == '-') k = -1;
        for(int i = k == 1 ? 0 : 1; s[i]; ++i) {
            x = (x<<3) + (x<<1) + mp1[s[i]];
        }
        return x*k;
    };

    auto toStr = [&mp2](long long num, char* ans) {
        long long idx = 0, k = 1;
        if(num < 0) {
            k = -1;
            num = -num;
        }
        while(num) {
            ans[idx++] = mp2[num%10];
            num /= 10;
        }
        if(k == -1)
            ans[idx++] = '-';
        reverse(ans, ans+idx);
        ans[idx++] = '\0';
        return ans;
    };

    int T; scanf("%d", &T);
    while(T--) {
        char s[maxn], t[maxn];
        scanf("%s%s", s, t);
        long long x = toNum(s);
        long long y = toNum(t);

        char ans[maxn];
        toStr(x+y, ans);
        printf("%s\n", ans);
        toStr(x-y, ans);
        printf("%s\n", ans);
        toStr(y-x, ans);
        printf("%s\n", ans);
    }
    return 0;
} 

第二题

最大子段和的变种
但是变得没做出来
主要是第一思路错了后面全都跟着错
大意是给一个长度为n的数组
求两个长度不超过m的子段，使得两个子段之和最大
子段可以为空

两个子段跟一个子段的求法是一样的，两个子段相当于是从a[0..i]和a[i..n]各求一遍最大值
主要是限制子段长度不超过m

最大字段和是dp经典题，dp[i] = max(dp[i-1] + a[i], a[i])
但是这个dp方程也能解释为贪心，贪心策略是：到第i位为止，如果前面的能让我增大(dp[i-1]>0)，我就要(dp[i-1]+a[i])，否则我就不要(a[i])
最开始没反应过来，以为限制子段长度就是当子段大于m的时候从dp[i]中减去a[i-m]，即

if(len >= m)
    dp[i] = max(dp[i-1]+a[i], a[i]) - a[i-m];

后来才发现错的很严重
之后再想找新思路时间已经不够了
代码就不贴了。。。我再想想