题意: 有n*m的矩阵,然后你有k发子弹。现在你可以朝着任意列发射子弹,每一发子弹都会使该列上的数-1,最小减少到0。 现在问你连续最长的行数,在k发子弹内,使得这些行上的数全部为0. 思路: 看了别人代码,其实RMQ不是必要的,开m个双端队列也可以。因此
题意:
有n*m的矩阵,然后你有k发子弹。现在你可以朝着任意列发射子弹,每一发子弹都会使该列上的数值-1,最小减少到0。
现在问你连续最长的行数,在k发子弹内,使得这些行上的数值全部为0.
思路:
看了别人代码,其实RMQ不是必要的,开m个双端队列也可以。因此每次要问一段范围内的最大值都是按顺序下去的,队列可以解决。
二分长度len,枚举n行是否存在这样的i~i+len-1,所需要的子弹数
code:
#include <bits> using namespace std; typedef long long LL; const int MAXN = 1e5+5; const int MAXM = 5; int a[MAXN][5]; int dp[5][MAXN][20]; //five RMQ int res[MAXM], tres[MAXM]; int n, m, k; void RMQ(int t) { for(int i = 0;i <br> <br> </bits>