题目传送门

这是一个二分+死dp！

真的很难想到二分……

正解思路

首先，我们可以用二分确定答案，我们发现去check一个ans，然后看有没有一条路径大于ans的个数大于等于k
为什么是这样？
如果你直接判断答案，是没有单调的
但是你判断答案是不是啊大于ans的，就是有单调性的~~至少能写出check函数~~
如果有，ans就可行
不然……

代码如下

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

int n,k;
int a[1001][1001];
int dp[1001][1001];

bool check(int t){
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]>=t){
                dp[i][j]=max(dp[i][j-1],dp[i-1][j])+1;
            }else{
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    return dp[n][n]>=k;
}

signed main(){
    freopen("shun.in","r",stdin);
    freopen("shun.out","w",stdout);
    cin>>n>>k;
    int l=0,r=1e9+1;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)
        cin>>a[i][j];
    while(l+1<r){
        int m=l+r>>1;
        if(check(m)) l=m;
        else r=m;
    } 
    //check(7);
    cout<<l<<endl;
}