题目内容
33DAI 进入了一个\(n\)行\(n\)列的二维数组。数组中每个位置都有一只羊，第\(i\)行第\(j\)列的羊的重量是\(a_{i,j}\)。
33DAI 一开始在\(a_{1,1}\)的位置，每次可以往右一步或者往下一步。即可以从\(a_{x,y}\)走到\(a_{x+1,y}\)或者\(a_{x,y+1}\)。但是不能走出这个数组，即不能走到下标小于\(1\)或大于\(n\)的位置。他走到\(a_{n,n}\)就会停下。
他每次到达一个位置就会牵走那里的羊，显然最终他一共走了\(2n-1\)步，牵走了\(2n-1\)头羊。33DAI 会在这些羊中拿出最重的\(k\)只羊送给 Kitten 作为她 10 月 9 日的生日礼物。他希望这些羊都足够重，他想知道所有牵羊方案中，哪种方案的最重的\(k\)只羊中最轻的那只羊最重。
说人话就是，从\(a_{1,1}\)走到\(a_{n,n}\)，每次只能向右或者向下，求路径上的数中的第\(k\)名最大是多少。
题目分析
这道题是求某个数的最大值，可以很自然地联想到二分答案。
我们可以看到\(a_{i,j}\)的范围是\([1,10^9]\)对值域二分后还可以有一个\(Θ(n^2)\)的操作，而我们的二分\(ch(x)\)的意思是验证从\(a_{1,1}\)到\(a_{n,n}\)存在着一条路径，使得路径上有不少于\(k\)个点使得这些点的权值大于或等于\(x\)，于是可以考虑动态规划。
定义动态规划数组\(f_{i,j}\)为从\(a_{1,1}\backsim a_{i,j}\)的路径上至多有几个\(\ge x\)的点。很显然，递推方程式为\(f_{i,j}=max(f_{i-1,j},f_{i,j-1})+(a_{i,j}\ge x)\)。
然后返回\((f_{n,m}\ge m)\)
顺便提一嘴，\(f_{i,j}\)的初始值全是零。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,ans,a[1003][1003],f[1003][1003],maxa,l,r,mid;
int ch(int x){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) f[i][j]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=max(f[i-1][j],f[i][j-1])+(a[i][j]>=x);
// cout<<f[i][j]<<"\t";}
// cout<<"\n";}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]>=m) return 1;}}return 0;
}
int main()
{cin>>n>>m;for(i=1;i<=n;i++){for(j=1;j<=n;j++) scanf("%d",&a[i][j]),maxa=max(maxa,a[i][j]);}l=0,r=maxa;
// cout<<"\n"<<ch(4)<<"\n";while(l<r){mid=(l+r)/2;
// cout<<l<<" "<<mid<<" "<<r<<"\n";if(ch(mid)) l=mid;else r=mid-1;if(l==r-1){if(ch(r)) l=r;break;}}cout<<l;
}