BZOJ 1113: [Poi2008]海报PLA

1113: [Poi2008]海报PLA

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1025  Solved: 679
[Submit][Status][Discuss]

Description

N个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.

Input

第一行给出数字N,代表有N个矩形.N在[1,250000] 下面N行,每行给出矩形的长与宽.其值在[1,1000000000]2 1/2 Postering

Output

最少数量的海报数.

Sample Input

5
1 2
1 3
2 2
2 5
1 4
BZOJ 1113: [Poi2008]海报PLA

Sample Output

4
BZOJ 1113: [Poi2008]海报PLA

HINT

 

Source

 

[Submit][Status][Discuss]

分析

单调栈

代码

 /*<--- Opinion --->*/

    #define HEADER
#define MYMATH
// #define FILEIO
// #define FSTREAM
// #define FREOPEN
#define FASTREAD
#define SHORTNAME ///// HEADER FILE ///// #ifdef HEADER #include <cmath>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm> #include <sstream>
#include <fstream>
#include <iostream> #include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <functional> #endif ///// SHORTNAME ///// #ifdef SHORTNAME #define LL long long
#define ll long long
#define re register
#define un unsigned
#define rb re bool
#define ri re int
#define ui un int
#define rl re LL
#define ul un LL #define rep (x, y) for (ri i = x; i <= y; ++i)
#define repi(x, y) for (ri i = x; i <= y; ++i)
#define repj(x, y) for (ri j = x; j <= y; ++j)
#define repk(x, y) for (ri k = x; k <= y; ++k) #define upto(x) for (ri i = 1; i <= x; ++i)
#define dnto(x) for (ri i = x; i >= 1; --i) #define up(x) for (ri i = 1; i <= x; ++i)
#define dn(x) for (ri i = x; i >= 1; --i) #define put(x) printf("%lld ", (LL)x)
#define putln(x) printf("%lld\n", (LL)x) #endif ///// FASTREAD ///// #ifdef FASTREAD const int FR_lim = ; char *FR_c; inline void fsetup(FILE *FR_file)
{
FR_c = new char[FR_lim];
fread(FR_c, , FR_lim, FR_file);
} template <class T>
inline void fread(T &FR_num)
{
FR_num = ; rb FR_neg = ; while (*FR_c < '')
if (*FR_c++ == '-')
FR_neg ^= true; while (*FR_c >= '')
FR_num = FR_num* + *FR_c++ - ''; if(FR_neg)FR_num = -FR_num;
} #endif ///// FILE I/O ///// #ifdef FILEIO FILE *FIN = fopen("input.txt", "r");
FILE *FOUT = fopen("output.txt", "w"); #ifndef FSTREAM #define fin FIN
#define fout FOUT #endif #endif ///// FSTREAM ///// #ifdef FSTREAM std::ifstream fin("input.txt");
std::ofstream fout("output.txt"); #endif ///// MYMATH ///// #ifdef MYMATH #define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b) #define Min(a, b) a = min(a, b)
#define Max(a, b) a = max(a, b) #define abs(x) (x < 0 ? -x : x) #define sqr(x) ((x)*(x)) #endif ///// _MAIN_ ///// void _main_(void); signed main(void)
{ #ifdef FREOPEN
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif _main_(); #ifdef FILEIO
fclose(FIN);
fclose(FOUT);
#endif #ifdef FREOPEN
fclose(stdin);
fclose(stdout);
#endif #ifdef FSTREAM
fin.close();
fout.close();
#endif return ;
} /*<--- Main --->*/ #define N 250005 int n;
int ans;
int h[N];
int stk[N];
int tot = ; void _main_(void)
{
fsetup(stdin); fread(n); ri x; up(n)
{
fread(x); fread(x);
while (tot && stk[tot] > x)--tot;
if (tot && stk[tot] == x)++ans;
stk[++tot] = x;
} putln(n - ans);
}

BZOJ_1113.cpp

好像那天特别高兴的样子,不知不觉就敲了个不明所以的模板, 补一份正常的代码。

 #include <bits/stdc++.h>
signed main(void) {
int n, tot = ;
scanf("%d", &n);
std::stack<int> stk;
for (int i = ; i <= n; ++i) {
int h; scanf("%*d%d", &h);
while (!stk.empty() && h < stk.top())
stk.pop();
if (!stk.empty() && h == stk.top())
++tot;
stk.push(h);
}
printf("%d\n", n - tot);
}

BZOJ_1113.cpp

@Author: YouSiki

上一篇:[转]PHP与Shell交互


下一篇:给Macbook Pro更换固态硬盘并转移系统的最简单办法