谁能帮我看一下这一题?我不知道怎样写。
原题:
#include
using namespace std;
struct node {
int r, h;
} b[200010];
int T,;
bool s[200010];
inline int read() {
char c = getchar();
int x = 0, s = 1;
while (c < '0' || c > '9') {
if (c == '-') s = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * s;
}
bool cmp_r(node a, node b) {
return a.r < b.r;
}
bool cmp_h(node a, node b) {
return a.h > b.h;
}
int main() {
T = read();
for (int i = 0; i < T; i++) {
b[i].r = read();
b[i].h = read();
}
node *a = new node [T];
memset(s, 0, sizeof(s));
sort(b, b + T, cmp_r);
for (int i = 0; i < T; i++)
if (s[i]) a[i].h = b[i].h;
sort(a, a + n, cmp_h);
delete[] a;
return 0;
}
贪心。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
int r[N], h[N];
int a[N];
bool cmp(int x, int y)
{
return h[x] < h[y];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%d%d", &r[i], &h[i]);
int res = 0;
for (int i = 1; i <= n; i ++ )
{
a[i] = 1; // 初始值为 1,因为至少可以垒出 1 层
for (int j = 1; j < i; j ++ )
if (r[i] > r[j])
a[i] = max(a[i], a[j] + 1);
res = max(res, a[i]);
}
printf("%d\n", res);
return 0;
}