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;
}