S 老师的签到

开始一看是动规的数字三角形的板子题，发现空间太大吃了一个罚时，之后，考虑对答案字符串每一个位置进行优化，发现需要考虑位置的可连接性，于是又吃一个罚时，再然后考虑深搜，优化了好几遍还是吃了几个罚时结束。

最后还是用到了数字三角形的动规并考虑了位置的可连续性，然后优化了好几次边界问题，感觉有点儿像瞎搞，不过最后还是过了。

贴一下代码吧：

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
char mp[N][N];
int v[N*4];
string ans;
int n, m, k;
typedef pair<int, int> p;
p q[N * 2 + 10][2*N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    for (int i = 0; i <= n + m - 2; i++)
        ans += 'z';
    ans[0] = mp[1][1];
    v[0] = 1;
    q[0][1] = {1, 1};
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i == 1 && j == 1)
                continue;
            if (ans[i + j - 2] >= mp[i][j] || i + j - 2 > k)
            {
                bool flag = 0;
                for (int m = 1; m <= v[i + j - 3]; m++)
                {
                    auto k = q[i + j - 3][m];
                    if (i - 1 == k.first && j == k.second)
                    {
                        flag = 1;
                        break;
                    }
                    else if (i == k.first && j - 1 == k.second)
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag && (ans[i + j - 2] > mp[i][j] || i + j - 2 > k))
                {
                    k = i + j - 2;
                    v[i + j - 2] = 0;
                    ans[i + j - 2] = mp[i][j];
                    q[i + j - 2][++v[i + j - 2]] = {i, j};
                }
                if (flag && ans[i + j - 2] >= mp[i][j])
                {
                    ans[i + j - 2] = mp[i][j];
                    q[i + j - 2][++v[i + j - 2]] = {i, j};
                }
            }
        }
    }
    cout << ans;
    return 0;
}