POJ 2533 / ZOJ 2136
Longest Ordered Subsequence Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 11175 Accepted: 4720
Description
A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence (a1, a2, …, aN) be any sequence (ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.Sample Input
71 7 3 5 9 4 8
Sample Output
4Source
Northeastern Europe 2002, Far-Eastern Subregion/**
Input:
12
16 78 10 69 64 10 27 10 70 45 5 35
Output:
3
**/
// author: jfo()
////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N;
typedef vector<int> T;
T a;
T o;
T v;
int f[1000][10001];
int dfs(unsigned int index, int val)
{
if(index >= v.size())
return 0;
if(val >= 0 && f[index][val] >= 0)
return f[index][val];
int d;
if(v[index] <= val) {
d = dfs(index + 1, val);
}
else {
int a = dfs(index + 1 ,v[index]) + 1;
int b = dfs(index + 1, val);
d = a > b ? a : b;
}
if(val >= 0)
f[index][val] = d;
return d;
}
// Longest Incremental Sequence
int LIS(const T& s, T& out)
{
v = s;
for(int i = 0; i < 1000; i++)
memset(f[i], -1, sizeof(f[i]));
return dfs(0, -1);
}
// another way (Java)
public void LIS2(E[] L)
{
int n = L.length;
int[] f = new int[n];//用于存放f(i)值；
f[0]=1;//以第a1为末元素的最长递增子序列长度为1；
for(int i = 1;i<n;i++)//循环n-1次
{
f[i]=1;//f[i]的最小值为1；
for(int j=0;j<i;j++)//循环i 次
{
if(L[j]<L[i] && f[j]>f[i]-1)
f[i]=f[j]+1;//更新f[i]的值。
}
}
System.out.println(f[n-1]);
}
// Longest Common Sequence
int LCS(const T& a, const T& b, T& out)
{
int len1 = a.size();
int len2 = b.size();
int L[2];
L[0] = new int[len2 + 1];
L[1] = new int[len2 + 1];
memset(L[0], 0, sizeof(L[0][0]) (len2 + 1));
memset(L[1], 0, sizeof(L[1][0]) * (len2 + 1));
int flag = 1;
int i, j;
for(i = 0; i < len1; i++) {
for(j = 0; j < len2; j++) {
if(a[i] == b[j])
L[flag][j + 1] = L[1 - flag][j] + 1;
else
L[flag][j + 1] = max(L[1 - flag][j + 1], L[flag][j]);
}
flag = 1 - flag;
}
int ret = L[1 - flag][j];
delete [] L[0];
delete [] L[1];
return ret;
}
#include <time.h>
void test()
{
srand( (unsigned)time( NULL ) );
int cases = 100;
while(cases– > 0) {
a.clear();
N = rand() % 20 + 5;
for(int i = 0; i < N; i++)
a.push_back(rand() % 100);
int r1 = LIS(a, o);
T b(a);
sort(b.begin(), b.end());
T::iterator iter = unique(b.begin(), b.end());
b.erase(iter, b.end());
int r2 = LCS(a, b, o);
copy(a.begin(), a.end(), ostream_iterator<int>(cout, " "));
cout << endl;
cout << "N: " << N << endl;
cout << "LIS: " << r1 << endl;
cout << "LCS: " << r2 << endl;
cout << "————————————" << endl;
if(r1 != r2)
break;
}
}
int solve()
{
int t;
cin >> N;
for(int i = 0; i < N; i++) {
cin >> t;
a.push_back(t);
}
// cout << LIS(a, o) << endl;
T b(a);
sort(b.begin(), b.end());
T::iterator iter = unique(b.begin(), b.end());
b.erase(iter, b.end());
cout << LCS(a, b, o) << endl;
return 0;
}
int main()
{
// test();
solve();
return 0;
};
说明：
Longest Common Sequence方法： Memory:260K Time:0MS
Longest Incremental Sequence方法：Memory:39456K Time:360MS
关于LCS：
Longest Incremental Sequence使用动态规划，
f(i, val)：从下标为i的元素开始，比val大的递增子序列最长长度；
f(0, -1)就是所求。
问题1.造桥问题. 原题是这样:Building Bridges. Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) … a(n) and n cities on the northern bank with x-coordinates b(1) … b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank. (Note: this problem was incorrectly stated on the paper copies of the handout given in recitation.)
大致就是要在一条河的南北两边的各个城市之间造若干座桥．桥两边的城市分别是a(1)…a(n)和b(1)…b(n).这里的要求a(i)只可以和b(i)之间造桥,同时两座桥之间不能交叉.希望可以得到一个尽量多座桥的方案.
比如上面这张图,初看上去让人有些没有思路.但是仔细一想,其实这就是一个完美的最长公共子序列的问题的变形.怎么讲呢?如果把河南边的a城市做一 个排序,可以得到一个序列.如上图,我们得到的就是S1 = {2,1,3,5,4}在这里,同时北边也进行依次排序,得到序列S2 = {1,2,5,4,3}.进一步从南边的第一座桥开始计算在北边序列中的index.也就是S1中的每个值相对于S2中的位置.比如说A2在南边是第一个 在北边是第二个,所以第一个元素是2.A1在北边的对应位置是1.A3在北边的对应位置是5,A5在北边的对应位置是3,最后一个A4在北边的对应位置是 3.这样我们就得到一个新的序列S3= {2,1,5,3,4}.这个序列的实际意义就是南边的第几座桥需要连接到北边的第几座桥.做理想的情况就是递增的,那样所有的桥都可以建造:)也就是说 我们的造桥问题就转化成了寻找这个序列的最长递增子序列的问题.当然就是{1,3,4}.也就是红线所代表的桥.
问题2.Box Stacking. You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
这个问题的简要描述就是有若干个不同的箱子.你需要把他叠放的尽量的高.但是箱子的摆放必须满足大的在下面,小的在上面的原则.箱子可以旋转且数量不限.要求给出一组箱子就能求出能摆放的最大高度。
箱子的长宽高分别是h,w,d.为了避免重复计算,我们约定w<=d.这样每个箱子可以改成3个箱子
动态规划：
H(i, (w,d)) 表示从下标为i的箱子开始，其上可放箱子的最大高度，其中约束条件为长宽(w,d)
