감 ¶
Greedy 고 근. . Dynamic Programming . Dynamic Programming 경 기 감 . Introduction To Algorithm Dynamic Programing 공 . 게 기 Weight 과 IQ . 그 " " Longest Common Subsequence 고, LCS Dynamic Algorithm 게 . 게 거, IQ 기 LCS 기 과 간 .
{{| 2005/07/09 Accepted 0:00.035 64 |}}
lcs_length cost table 과 running time O(n*n), memory cost O(n*n). 그고 print_lcs longest path 거 running time O(n + n) = O(n).
고 .
ver1 (Greedy Algorithm) ¶
고 .
~cpp
//no 10131
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
fstream fin("input.txt");
const int MAX_ELEPHANT = 1100;
struct Elephant
{
int index;
int weight;
int IQ;
bool operator () (const Elephant & a, const Elephant & b)
{
if (a.weight < b.weight)
return true;
else if (a.weight == b.weight)
{
if (a.IQ > b.IQ)
return true;
}
return false;
}
};
int input_elephant_info(Elephant * e);
void count_elephant(Elephant * elephant, int num_elephant);
int main()
{
Elephant elephant[MAX_ELEPHANT];
int num_elephant = input_elephant_info(elephant);
sort(&elephant[0], &elephant[num_elephant], Elephant());
count_elephant(elephant, num_elephant);
return 0;
}
int input_elephant_info(Elephant * e)
{
int count = 0;
while (fin >> e[count].weight >> e[count].IQ)
{
e[count].index = count + 1;
count++;
fin.get();
if (fin.peek() == EOF)
break;
}
return count;
}
void count_elephant(Elephant * e, int num)
{
// test
// for (int t = 0; t < num; t++)
// {
// cout << e[t].index << " " << e[t].weight << " " << e[t].IQ << endl;
// }
// end
int max_count = 0;
int count;
vector<int> v_temp;
vector<int> result;
result.reserve(MAX_ELEPHANT);
v_temp.reserve(MAX_ELEPHANT);
Elephant temp;
int i;
for (int k = 0; k < num - 1; k++)
{
temp.weight = e[k].weight;
temp.IQ = e[k].IQ;
v_temp.push_back(e[k].index);
count = 1;
for (i = k + 1; i < num; i++)
{
if (temp.weight >= e[i].weight || temp.IQ <= e[i].IQ)
continue;
temp.weight = e[i].weight;
temp.IQ = e[i].IQ;
count++;
v_temp.push_back(e[i].index);
}
if (count > max_count)
{
max_count = count;
result = v_temp;
}
v_temp.clear();
}
cout << max_count << endl;
for (i = 0; i < max_count; i++)
cout << result[i] << endl;
}
ver2. Dynamic Algorithm ¶
~cpp
//no 10131
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_ELEPHANT = 1010;
const int WEIGHT = 1;
const int IQ = 2;
int TYPE_SORT;
struct Elephant
{
short index;
short weight;
short IQ;
bool operator () (const Elephant & a, const Elephant & b)
{
if (TYPE_SORT == WEIGHT)
{
if (a.weight < b.weight)
return true;
else if (a.weight == b.weight && a.IQ <= b.IQ)
return true;
return false;
}
else
{
if (a.IQ > b.IQ)
return true;
else if (a.IQ == b.IQ && a.weight > b.weight)
return true;
return false;
}
}
};
Elephant elephant_weight[MAX_ELEPHANT];
Elephant elephant_IQ[MAX_ELEPHANT];
int num_elephant;
vector <int> result;
int input_elephant_info();
void sort_elephant();
int lcs_length(unsigned char t[][MAX_ELEPHANT]);
void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT]);
void print_route(int len);
int main()
{
unsigned char table[MAX_ELEPHANT][MAX_ELEPHANT];
num_elephant = input_elephant_info();
sort_elephant();
int len = lcs_length(table);
print_lcs(num_elephant, num_elephant, table);
print_route(len);
return 0;
}
int input_elephant_info()
{
int count = 0;
while (cin.peek() != EOF)
{
count++;
cin >> elephant_weight[count].weight >> elephant_weight[count].IQ;
elephant_weight[count].index = count;
elephant_IQ[count] = elephant_weight[count];
cin.get();
}
return count;
}
void sort_elephant()
{
TYPE_SORT = WEIGHT;
sort(&elephant_weight[1], &elephant_weight[num_elephant+1], Elephant());
TYPE_SORT = IQ;
sort(&elephant_IQ[1], &elephant_IQ[num_elephant+1], Elephant());
}
int lcs_length(unsigned char t[][MAX_ELEPHANT])
{
int i, j;
for (i = 0; i <= num_elephant; i++)
t[0][i] = t[i][0] = 0;
for (i = 1; i <= num_elephant; i++)
{
for (j = 1; j <= num_elephant; j++)
{
if (elephant_weight[i].index == elephant_IQ[j].index)
t[i][j] = t[i-1][j-1] + 1;
else if (t[i-1][j] >= t[i][j-1])
t[i][j] = t[i-1][j];
else
t[i][j] = t[i][j-1];
}
}
return t[i-1][j-1];
}
void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT])
{
if (i == 0 || j == 0)
return;
if (elephant_weight[i].index == elephant_IQ[j].index)
{
print_lcs(i-1, j-1, t);
result.push_back(elephant_weight[i].index);
}
else if (t[i-1][j] >= t[i][j-1])
print_lcs(i-1, j, t);
else
print_lcs(i, j-1, t);
}
void print_route(int len)
{
cout << len << endl;
for (int i = 0; i < len; i++)
cout << result[i] << endl;
}
