A：使每一列严格递增的最少操作次数

知识点：二维数组、贪心

思路：由于我们只能变大，不能变小，那么第一个数肯定不需要变。对于后面的每个数x：如果它比前一个数pre大，那么不变。否则，x至少要增大到pre+1, 才能保持严格递增，增大到恰好等于pre+1是最优秀的(不然后面的数需要变得更大)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][55],ans=0;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]<=a[i-1][j]){
                ans+=a[i-1][j]-a[i][j]+1;
                a[i][j]=a[i-1][j]+1;
            }
        }
    }
    cout<<ans;
    return 0;
}

B：从盒子中找出字典序最大的字符串

知识点：枚举、字符串

思路：如果固定子串的左端点，那么子串越长，字典序越大。

所以核心思路是：枚举子串的左端点，计算最大子串。单个子串的长度不能超过多少？由于其余 k−1 个子串必须是非空的，取长度为 1，其余子串的长度之和至少为 k−1。所以单个子串的长度至多为 n−(k−1)。

注意特判 k=1 的情况，此时无法分割（子串左端点只能是 0），所以答案是 s。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
string f(string w, int n) {
    if(n==1) return w;
    string s="";
    for(int i=0; i<w.size(); i++)
        s=max(s,w.substr(i,w.size()-n+1));
    return s;
}
int main() {
    cin>>s>>n;
    cout<<f(s,n);
    return 0;
}

C：矩阵中的最长递增路径

知识点：记忆化搜索

思路：题目要找的是连续递增的序列，且方向只能是上，下，左，右4个方向，所以可以先从一个格子开始找，对比它4周的格子，有没有比它小的，如果有，比如有A，B，C三个格子都比它小，那么当前格子的最大连续递增长度就是这3个格子的最大连续递增长度中的最大值+1，但是考虑到超时问题，需要用一个二维数组进行标记，看看本次走到了i,j位置时最大连续递增长度是否有数据，若有直接返回，若没有继续搜索。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[201][201],f[201][201]= {0},d[][2]= {{0,1},{0,-1},{1,0},{-1,0}},ret;
int dfs(int x,int y) {
    if(f[x][y])return f[x][y];
    for(int i=0; i<4; i++) {
        int xx=x+d[i][0],yy=y+d[i][1];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[x][y]>a[xx][yy])
            f[x][y]=max(f[x][y],dfs(xx,yy));
    }
    return f[x][y]+=1;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            ret=max(ret,dfs(i,j));//从i,j的位置进行搜索
    cout<<ret;
    return 0;
}

D：花匠

知识点：最长上升/下降子序列

思路：求一个最长子序列的长度，要求任意三个数，中间的那个数是三个数中最大或者最小的那个数。可以使用最长上升子序列以及最长下降子序列，最后取最大值就可以了。

设计 f[i] 表示前 i 个元素中的最长上升子序列长度。

设计 g[i] 表示前 i 个元素中的最长下降子序列长度。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[2000001],f[2000001]={0,1},g[2000001]={0,1};
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=2;i<=n;i++){
        if(a[i]>a[i-1]) f[i]=g[i-1]+1;
        else f[i]=f[i-1];
        if(a[i]<a[i-1]) g[i]=f[i-1]+1;
        else g[i]=g[i-1];
    }
    cout<<max(f[n],g[n]);
    return 0;
}