A题

注意到横坐标和纵坐标其实是独立不影响的。只要知道了某一列有哪些连续的格子，就可以知道某一步应该走到哪里。这种思想在很多题目都出现过。

接下来变成了维护一些不相交区间，要支持快速查询某个点的左边和右边是否有区间，并且插入/合并区间。用set来实现。注意使用哨兵元素处理迭代器运算异常减少代码量。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
char op[maxn];
typedef set<pair<int,int> > spi;
spi r[maxn], c[maxn];
void add(spi &s, int pos)
{
    int l = pos, r = pos;
    auto it = s.lower_bound({pos, pos});
    auto jt = it--; // jt: >=   it <=
    if(it->second == pos - 1) l = it->first;
    if(jt->first == pos + 1) r = jt->second;
    s.insert({l, r});
    if(l != pos) s.erase(it); 
    if(r != pos) s.erase(jt); 
}
void move(spi &s, int &pos, int dir)
{
    if(dir == -1)
    {
        auto it = s.lower_bound({pos, pos});
        it--;
        if(it->second == pos - 1) pos = it->first - 1;
        else pos = pos - 1;
    }
    else 
    {
        auto it = s.lower_bound({pos, pos});
        if(it->first == pos + 1) pos = it->second + 1;
        else pos = pos + 1;
    }
}
int main()
{
    int T; cin >> T;
    for(int cas = 1; cas <= T; cas++)
    {
        int q, n, m, x, y;
        scanf("%d%d%d%d%d", &q, &n, &m, &x, &y);
        scanf("%s", op + 1);
        for(int i = 1; i <= n; i++) r[i].clear(), r[i].insert({-1e9,-1e9}), r[i].insert({1e9,1e9});
        for(int i = 1; i <= m; i++) c[i].clear(), c[i].insert({-1e9,-1e9}), c[i].insert({1e9,1e9});
        for(int i = 1; i <= q; i++)
        {
            int dx = x, dy = y;
            if(op[i] == 'N') // up
                move(c[dy], dx, -1);
            else if(op[i] == 'S') // down
                move(c[dy], dx, 1);
            else if(op[i] == 'W') // left
                move(r[dx], dy, -1);
            else // right
                move(r[dx], dy, 1);
            add(c[y], x), add(r[x], y);
            x = dx, y = dy;
            //cerr << x << " " << y << ">" << r[x].size() << endl;
        }
        printf("Case #%d: %d %d\n", cas, x, y);
    }
}

B题

题意说在一个大的矩形内取出一个小的矩形，使得每一行的极差不超过k。

考虑每一行，如果得到了每位置最多能往左边延伸多少。就可以用单调栈求出最大矩形面积了。

如何得到每个位置左边最多能延伸多长。双指针，l， r，用set维护[l, r]内的最大值，如果r - *set.begin() > k就不断移动l指针，并同时在set里删除l指针所在位置的值。最后r位置往坐最多延伸的就是位置l。

是否存在有目前r右边的数能延伸到l左边，不存在，因为若存在[l – x, r + x]的区间，已经覆盖了[l – x, r]区间，则区间内的极差已经不满足条件。

预处理复杂度n^2logn，完成后枚举横坐标，在每个横坐标往纵向做单调栈，总复杂度n^2logn + n^2

#include<bits/stdc++.h>
using namespace std;
int mp[303][303], len[303][303];
int s[303], w[303];
multiset<int> st;
int main()
{
    int T; cin >> T;
    for(int cas = 1; cas <= T; cas++)
    {
        int n, m, k;
        memset(len, 0, sizeof len);
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);
        for(int i = 1; i <= n; i++)
        {
            st.clear();
            int l = 1;
            for(int j = 1; j <= m; j++)
            {
                while(l < j && *st.begin() + k < mp[i][j]) st.erase(st.find(mp[i][l++]));
                len[i][j] = max(len[i][j], l);
                st.insert(mp[i][j]);
            }
            st.clear();
            l = 1;
            for(int j = 1; j <= m; j++)
            {
                while(l < j && *st.rbegin() > mp[i][j] + k) st.erase(st.find(mp[i][l++]));
                len[i][j] = max(len[i][j], l);
                st.insert(mp[i][j]);
            }
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++) len[i][j] = j - len[i][j] + 1;

        // for(int i = 1; i <= n; i++)
        //     for(int j = 1; j <= m; j++) printf("%d%c", len[i][j], " \n"[j == m]);

        int p = 0, ans = 0;
        for(int j = 1; j <= m; j++)
        {
            memset(s, 0, sizeof s);
            memset(w, 0, sizeof w);
            len[n + 1][j] = p = 0;
            for(int i = 1; i <= n + 1; i++)
            {
                if(len[i][j] > s[p]) s[++p] = len[i][j], w[p] = 1; 
                else 
                {
                    int wd = 0;
                    while(s[p] > len[i][j])
                    {
                        wd += w[p];
                        ans = max(ans, wd * s[p]);
                        p--;
                    }
                    s[++p] = len[i][j], w[p] = wd + 1;
                }
            }
        }
        printf("Case #%d: %d\n", cas, ans);
    }
}

C题

分组背包。难点在于处理最后一次不用回家的情况。

前后缀优化，正着算一次，倒着算一次。然后枚举最后一次所选择的颜色……

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 233;
int pos[maxn];
vector<int> c[maxn];
int f[maxn][maxn], g[maxn][maxn];
int main()
{
    int T; cin >> T;
    int cas = 0;
    while(T--)
    {
        int n, m; scanf("%d%d", &n, &m);
        for(int i = 1; i <= 1000; i++) c[i].clear();
        for(int i = 1; i <= n; i++) scanf("%d", &pos[i]);
        for(int i = 1; i <= n; i++)
        {
            int t; scanf("%d", &t);
            c[t].push_back(pos[i]);
        }
        for(int i = 1; i <= 1000; i++) sort(c[i].begin(), c[i].end());
        memset(f, 0x3f, sizeof f);
        memset(g, 0x3f, sizeof g);
        f[0][0] = 0; g[1001][0] = 0;
        //for(int i = 0; i < c[3].size(); i++) cout << c[3][i] << ' '; puts("");
        for(int i = 1; i <= 1000; i++)
        {
            for(int j = 0; j <= m; j++)
            {
                f[i][j] = f[i - 1][j];
                for(int k = 0; k < c[i].size(); k++)
                {
                    int t = k + 1;
                    if(j - t >= 0)
                        f[i][j] = min(f[i][j], f[i - 1][j - t] + c[i][k] * 2);
                }
            }
        }
        //cout << f[1000][3] << endl;
        for(int i = 1000; i; i--)
        {
            for(int j = 0; j <= m; j++)
            {
                g[i][j] = g[i + 1][j];
                for(int k = 0; k < c[i].size(); k++)
                {
                    int t = k + 1;
                    if(j - t >= 0)
                        g[i][j] = min(g[i][j], g[i + 1][j - t] + c[i][k] * 2);
                }
            }
        }
        //cout << g[1][3] << endl;
        int ans = INT_MAX;
        for(int i = 1; i <= 1000; i++)
        {
            for(int j = 0; j < c[i].size() && j <= m; j++)
            {
                for(int k = 0; k <= 1000; k++)
                {
                    if(m - k - j - 1 >= 0)
                    ans = min(ans, f[i - 1][k] + g[i + 1][m - k - j - 1] + c[i][j]);
                }
            }
        }
        printf("Case #%d: %d\n", ++cas, ans);
    }
}