codeforces 514d R2D2 and Droid Army (RMQ+二分）

题意： 有n*m的矩阵，然后你有k发子弹。现在你可以朝着任意列发射子弹，每一发子弹都会使该列上的数-1，最小减少到0。 现在问你连续最长的行数，在k发子弹内，使得这些行上的数全部为0. 思路： 看了别人代码，其实RMQ不是必要的，开m个双端队列也可以。因此

题意：

有n*m的矩阵，然后你有k发子弹。现在你可以朝着任意列发射子弹，每一发子弹都会使该列上的数值-1，最小减少到0。

现在问你连续最长的行数，在k发子弹内，使得这些行上的数值全部为0.

思路：

看了别人代码，其实RMQ不是必要的，开m个双端队列也可以。因此每次要问一段范围内的最大值都是按顺序下去的，队列可以解决。

二分长度len，枚举n行是否存在这样的i~i+len-1，所需要的子弹数<=k，存在则表示len可行。

code：

#include 
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 < n; i++) 
        dp[t][i][0] = a[i][t];

    for(int j = 1;(1<
声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn核实处理。
专题推荐：codeforces 514d R2D2 and Droid

			   上一篇：cocos2d-x-2.2.0
			   下一篇：2dx 分辨率