HDU1257

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x7fffffff;
const int maxn = 30100;

int h[maxn];// the height.
int d[maxn];

int main()
{
    int n;
    int idx = 1;
    while(scanf("%d", &n)!= EOF) {
        int cnt = 0;
        bool flag = false;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &d[i]);
        }
        for(int i = 1; i <= n; i++) {
            if(!flag) {
                flag = true;
                h[idx++] = d[1];
                cnt++;
            }
            else
            {
                int minh = INF;
                int index;
                for(int j = 1; j < idx; j++) {
                    if(h[j]>=d[i]) {
                        int t = h[j]-d[i];
                        if(t<minh) {
                            minh = t;
                            index = j;
                        }
                    }
                }
                if(minh==INF) {
                    cnt++;
                    h[idx++] = d[i];
                } else {
                    h[index] = d[i];
                }
            }
        }
        printf("%d\n", cnt);
        for(int t = 1; t < idx; t++) h[t] = 0;
    }
    return 0;
}
/**
5 1 2 3 4 5
8 9 8 6 4 10 2 5 4
8 389 207 155 300 299 170 158 65
**/

HDU1257,布布扣,bubuko.com

HDU1257

原文：http://blog.csdn.net/achiberx/article/details/23198435