ホームページ > データベース > mysql チュートリアル > codeforces 514d R2D2 and Droid Army (RMQ+二分)

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

WBOY
リリース: 2016-06-07 15:00:54
オリジナル
1341 人が閲覧しました

题意: 有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>
ログイン後にコピー
関連ラベル:
and
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート