right ble out max 属性 ret sci write
题意:
有一些木棍,每个有长度和重量,要求把这些木棍排成若干两个属性值均不下降的序列。问至少要分为多少个序列。且要保证排出来的子序列数最少。
思路:
(9 , 4) ,(2 , 5) ,(1 , 2) ,(5 , 3),(4 , 1) 可以排成这样
(4 , 1) , (5 , 3) , (9 , 4); (1 , 2) , (2 , 5) .
其中:(4,1)<=(5,3)<=(9,4) 为不降序列,(4,1)<(5,3)由于 4<5&&1<3
(1,2)<(2,5)为不降序列。即最少的不降子序列为 2,输出 2
- #include < iostream > #include < algorithm > using namespace std;
- const int MAX = 5001;
- struct wooden {
- int l,
- w,
- flag;
- }
- wd[MAX];
- bool cmp(wooden x, wooden y) {
- if (x.l != y.l) return x.l < y.l;
- return x.w < y.w;
- }
- int main() {
- int T;
- cin >> T;
- while (T--) {
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> wd[i].l >> wd[i].w;
- wd[i].flag = 0;
- }
- sort(wd, wd + n, cmp);
- int res = 0;
- for (int i = 0; i < n; i++) {
- if (wd[i].flag) continue;
- res++;
- int cur = wd[i].w;
- for (int j = i + 1; j < n; j++) {
- if (!wd[j].flag && wd[j].w >= cur) {
- wd[j].flag = 1;
- cur = wd[j].w;
- }
- }
- }
- cout << res << endl;
- }
- return 0;
- }
POJ 1065 Wooden Sticks【贪心】
来源: http://www.bubuko.com/infodetail-2262974.html