SRM585 div2

250：题意：给你n个数，让你求这段数里有多少个单调递增序列

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <vector>
 7 using namespace std;
 8 
 9 class LISNumberDivTwo
10 {
11     public:
12            int calculate(vector<int>);
13 };
14 
15 int LISNumberDivTwo::calculate(vector<int>seq)
16 {
17     int n = seq.size();
18     int temp = 55;
19     int ret = 0;
20     for(int i=0; i<n; i++)
21     {
22         if(seq[i] <= temp)
23         {
24             ret++;
25         }
26         temp = seq[i];
27     }
28     return ret;
29 }

View Code

500: 题意：给你一个数，代表树的高度，然后问你最少要几个小车可以走完这个树；

找规律，找他树里面有多少个三脚叉，三脚叉最多的那层肯定是倒数第二层，然后不停减二，直到 n-2 < 0 ，然后再判断n是否等于1，等于1，说明

第一层那个点没算进来，所以要 ret++。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <cmath>
 8 using namespace std;
 9 
10 class TrafficCongestionDivTwo
11 {
12     public:
13            long long theMinCars(int);
14 };
15 
16 
17 long long TrafficCongestionDivTwo::theMinCars(int treeHeight)
18 {
19     long long ret = 0;
20     int n = treeHeight-1;
21     ret = (long long)pow((double)2,(double)n);
22     while(n-2>=0)
23     {
24         ret += (long long)pow((double)2,(double)n-2);
25         n = n - 2;
26     }
27     if(n!=0) ret++;
28     return ret;
29 }

View Code