dp + greedy实现
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 #include "nothing.h" 7 #include <string> 8 9 using namespace std; 10 11 int c[105][105]; 12 int dp_activity_selector(const vector<int> &s, const vector<int> &f, int beg_time, int end_time); 13 void activity_selector(const vector<int> &s, const vector<int> &f) 14 { 15 memset(c, -1, sizeof(c)); 16 dp_activity_selector(s, f, 0, f[f.size() - 1] + 1); 17 cout << "dp_activity_selector:" << c[0][f[f.size() - 1] + 1]; 18 } 19 20 int dp_activity_selector(const vector<int> &s, const vector<int> &f, int beg_time, int end_time) 21 { 22 int &ans = c[beg_time][end_time]; 23 if (ans >= 0)return ans; 24 if (beg_time >= end_time)return 0; 25 ans = 0;//必须初始化，不然可能return-1 26 27 for(int i=0;i<s.size();i++) 28 if (beg_time <= s[i] && end_time >= f[i]) 29 { 30 int ret = dp_activity_selector(s, f, beg_time, s[i]) + dp_activity_selector(s, f, f[i], end_time); 31 if (ret + 1 > ans)ans = ret + 1; 32 } 33 return ans; 34 } 35 36 void iterative_activity_selector(const vector<int> &s, const vector<int> &f) 37 { 38 const int n = s.size(); 39 int beg = f[0]; 40 int ans = 1; 41 for(int i=1;i<n;i++) 42 if (beg < s[i]) 43 { 44 ++ans; 45 beg = f[i]; 46 } 47 cout << "iterative_activity_selector:" << ans << endl; 48 } 49 50 51 int _recursive_activity_selector(const vector<int> &s, const vector<int> &f, int k, int cur_time); 52 void recursive_activity_selector(const vector<int> &s, const vector<int> &f) 53 { 54 cout << "recursive_activity_selector:" << _recursive_activity_selector(s, f, 0, 0) << endl; 55 } 56 57 int _recursive_activity_selector(const vector<int> &s, const vector<int> &f, int k, int cur_time) 58 { 59 if (k >= s.size())return 0; 60 if (s[k] >= cur_time) 61 return 1 + _recursive_activity_selector(s, f, k + 1, f[k]); 62 return _recursive_activity_selector(s, f, k + 1, cur_time); 63 }