这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
建议先看看前言:http://www.wutianqi.com/?p=2298
连载总目录:http://www.wutianqi.com/?p=2403
题目就不贴了,看书~~~
这个问题算是贪心算法中很经典的一道题目了。
按照书上所说,定义以下关系:
即:
如果按照DP来做,可以找到以下关系:
不过,看看定理16.1(这个有必要自己仔细看看!)
它证明了为何这里可以用贪心。
Tanky Woo 标签: Tanky Woo,贪心算法,算法导论
(其实贪心这块和DP一样,很难说清楚,看多了,做多了,你就知道为何这个问题可以用DP,这个问题可以用贪心。。。)
下面贴出此题的代码:
#include
#include
using namespace std;
typedef struct Act{
int s; // start time
int f; // final time
}Act;
Act arr[100];
Act temp[100];
int n;
bool cmp(Act a, Act b)
{
return a.f < b.f;
}
int main()
{
//freopen("input.txt", "r", stdin);
cout << "输入活动个数: ";
cin >> n;
cout << "输入" << n << "个活动的开始和结束时间:" << endl;
for(int i=0; i> arr[i].s >> arr[i].f;
sort(arr, arr+n, cmp);
int k = 0;
temp[k] = arr[0];
for(int i=1; i= temp[k].f)
temp[++k] = arr[i];
cout << "选择的活动: " << endl;
for(int i=0; i<=k; ++i)
cout << temp[i].s << " " << temp[i].f << endl;
return 0;
}
结果如图: