题目传送门

这个题目放在T2有一点难！

首先，这给题目我赛中得了85分，T了三个点，也是单题全场最高分（意味着没人AC这道题）
我当时自以为自己是O（nm）的，其实string是有常数的，所以还是炸了

赛中思路

一眼dp，记录\(dp_{i,j}\)表示走到第\(i\)点和第\(j\)点的最小字符串是什么
转移方程就是\(dp_{i,j}=min(dp_{i-1,j},dp{i,j-1})+s_{i,j}(表示当前这个字符)\)。
但是你要知道，这是有常数的，所以还是被卡了。我还特地用了push_back，但是还是被卡了。
还有，这样写的话会MLE，然后我就滚动数组，因为我只需要上一列和上一行就可以了，那么空间就会省很多（意味着时间换空间）

代码如下

#include<bits/stdc++.h>
using namespace std;

void gmin(int &x,int y){x=min(x,y);}
void gmax(int &x,int y){x=max(x,y);}

string f[2005],g[2005],s[2005];

int main(){
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++) cin>>s[i];
    for(int i=0;i<=m;i++) for(int j=0;j<=m;j++)
        f[i]=g[i]="";
    for(int i=1;i<=m;i++){
        if(i==1){
            f[i]=s[0][i-1];
        }else{
            string x=f[i-1];
            x.push_back(s[0][i-1]);
            f[i]=x;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==1){
                string x=f[j];
                x.push_back(s[i-1][j-1]);
                g[j]=x;
            }else{
                string x=min(f[j],g[j-1]);
                x.push_back(s[i-1][j-1]);
                g[j]=x;
            }
        }
        for(int j=1;j<=m;j++) f[j]=g[j];
    }
    cout<<f[m]<<endl;
}

正解

为什么要dp？
原因在于你没有办法每一步都贪心的选一个最优的，所以你必须dp。
那么我们可以换一种角度，就是说我们一步一步枚举，然后枚举所有可以好k步可以走到的点。
这个时候如果一个点它的字母要比当前待更新的字母小，那么说明我们可以选它……

但是！

如果这个格子不可达，也就是说它上方的格子和它右方的格子没有走到，说明这个格子是不可到达的，也就是不优的！
那么如果这个格子的坐标合法，且可达。那么我们就可以更新答案。
最后我们每轮输出答案

还有最抽象的一步
就是说如果只有一个最有的，那么就是很健康了对吧。
但是如果有两个呢？
我们一步一步考虑
1.输出正常输出
2.你不能确定你一定会选择哪一个，因为有可能一个格子是的发展格都是z，而另一个是a，你是说不准的。
这个时候，只要不影响输出答案，那么我们把这些格子都算在考虑范围之内
它们终究会分出胜负的，就算没有，也不影响答案的输出。

所以正解代码如下

#include<bits/stdc++.h>
using namespace std;

const int N=2010;

int n,m;
char s[N][N];
bool vis[N][N];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>s[i]+1;
    cout<<s[1][1];
    vis[1][1]=1;
    for(int i=2;i<=n+m-1;i++){
        char ch='z';
        for(int x=1;x<=n;x++){
            int y=i+1-x;
            if(y<1||y>m) continue;
            if(vis[x-1][y]&&s[x][y]<ch) ch=s[x][y];
            if(vis[x][y-1]&&s[x][y]<ch) ch=s[x][y];
        }
        cout<<ch;
        for(int x=1;x<=n;x++){
            int y=i+1-x;
            if(y<1||y>m) continue;
            if(vis[x-1][y]&&s[x][y]==ch) vis[x][y]=1;
            if(vis[x][y-1]&&s[x][y]==ch) vis[x][y]=1;
        } 
    }
    cout<<endl;
}

很难想象TYWZ都是什么人？出这样的题做？