BabbleDay's Blog

Longest Increasing Subsequence

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Given a sequence , find the largest subset such that for every i < j, a_i < a_j.

O(nlogn) solution

Let A_i,j be the smallest possible tail out of all increasing subsequences of length j using elements .
A_i,j 在这里表示原数组里长度为j的递增子序列的可能的最小的末尾（例：对j=2有“14”和“13”则A_i,2表示3）
for any particular i, 这是观察所得规律，因其单增，故可用二分法
This suggests that if we want the longest subsequence that ends with a_{i + 1}, we only need to look for a j such that A_i,j < a_{i + 1} < = A_{i,j + 1} and the length will be j + 1.

Notice that in this case, A_{i + 1,j + 1} will be equal to a_{i + 1}, and all A_{i + 1,k} will be equal to A_i,k for .

Furthermore, there is at most one difference between the set A_i and the set A_{i + 1}, which is caused by this search.

Since A is always ordered in increasing order, and the operation does not change this ordering, we can do a binary search for every single .

Further explain:--GONG Zhi Tao 11:19, 1 August 2012 (EDT)

We have elements: .

And we have a longest increasing subsequences of them: , for any A_i,k(1 < = k < = j) you could not find a smaller alternative.

Now we have a new element: a_{i + 1}

What we can do about it:

1. insert it at the back if A_i,j < a_{i + 1}, where we will have a longer one;

2. make it an alternative for A_i,k if

Alternative means that we MIGHT get longer ones if using the new element.

http://blog.csdn.net/linulysses/article/details/5559262

具体实现代码，来自algorithmist

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
	vector<int> p(a.size());
	int u, v;
 
	if (a.empty()) return;
 
	b.push_back(0);
 
	for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
		if (a[b.back()] < a[i]) 
                {
			p[i] = b.back();
			b.push_back(i);
			continue;
		}
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
		for (u = 0, v = b.size()-1; u < v;) 
                {
			int c = (u + v) / 2;
			if (a[b[c]] < a[i]) u=c+1; else v=c;
		}
 
                // Update b if new value is smaller then previously referenced value 
		if (a[i] < a[b[u]]) 
                {
			if (u > 0) p[i] = b[u-1];
			b[u] = i;
		}	
	}
 
	for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
	int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
	vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
	vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
	for (size_t i = 0; i < lis.size(); i++)
		printf("%d ", seq[lis[i]]);
        printf("\n");    
 
	return 0;
}

题目不难，先排序再查找，对C++语言做点小结——Vector的使用

1. #include <vector>
2. vector<int> v;
3. v.clear();
4. v.resize(int n); 将vector的大小重置为n
5. v[int i] 可通过索引i直接获取内容
6. sort(a_vector.begin(), a_vector.end()) 调用函数排序，需要algorithm包 

真高兴又可以写解题心得了～因为上次经过不懈努力解决了自己的第一道动态规划所以又找来一道题练习，各种弯弯绕中获得了：

1. 动态规划的状态记录不要局限于一维：就是不要总想着建个struct来存各种信息，倒不如直接多维来的清晰

2. 记得每个变量都要初始话： 以前用无脑的java各种默认为零，现在不初始化的结果就是core dump，重点是还总是找不到错

3. 关于core dump：先查数组越界的问题，然后再看看栈溢出和指针神马的。。

4. 滚动数组实现： t 和 1-t，就能永远在0、1中间循环了

接下来是这道题：要求找到递增的子矩阵
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2494

算法核心是：
关注第i行从第j1列到第j2列是否递增，
    若否，break到j1+1的循环;
    若是，检查（i，j1）是否比（i-1，j2）大，
                    若是，当前滚动数组[j1][j2] = 原滚动数组[j1][j2] + j2 - j1 + 1;
                                                             // 原滚动数组[j1][j2]记录上一行及其之前行严格递增矩阵元素个数
                    若否，当前滚动数组[j1][j2] = j2 - j1 + 1;
                    将当前滚动数组[j1][j2] 和 输出结果比较取大

注意点：j2==j1时的情况， i==0时的情况

#include <iostream>
#include <cstring>

#define rep(i, s, t) for(int i=s; i<t; i++)

using namespace std;

void the_case(int n, int m)
{
    int in[n][m];
    int a[2][m][m];
    int t=0; //勿忘初始化
    int ans = 0;
    memset(a, 0, sizeof(a));
    rep(i, 0, n)
    {
        rep(j, 0, m)
        {
            cin >> in[i][j];
        }
    }
    rep(i, 0, n)
    {
        memset(a[t], 0, sizeof(a[t]));
        for (int j1=0; j1<m; j1++) 
        {
            if (i==0 || in[i][j1] > in[i-1][j1])
                a[t][j1][j1] = a[1-t][j1][j1] + 1;
            else a[t][j1][j1] = 1;
            if(ans<a[t][j1][j1]) ans = a[t][j1][j1];
            rep(j2, j1+1, m)
            {
                if(in[i][j2]>in[i][j2-1]) // j2==0越界
                {
                    if(i==0 || in[i][j1]>in[i-1][j2])
                        a[t][j1][j2] = a[1-t][j1][j2]+j2-j1+1;
                    else
                        a[t][j1][j2] = j2-j1+1;
                    if(ans<a[t][j1][j2]) ans = a[t][j1][j2];
                }
                else break;
            }
        }
        t = 1-t;
    }
    cout << ans << endl;
}

int main()
{
    int n,m;
    while(true)
    {
        cin >> n >> m;
        if(n==0 && m==0) break;
        else the_case(n,m);
    }
    return 0;
}

算法优化：

增加预处理：构建二维矩阵记录每个数从自身开始的连续最大递增序列长度（含自身）
遍历所有数， if (L[i][j1] > 1)
                         j2=j1+1 ----> j1+L[i][j1]
                              if (i!=0 && N[i][j1]>N[i-1][j2])
                                    a[t][j1][j2] = a[1-t][j1][j2] + j2 - j1 + 1;
                              else a[t][j1][j2] = j2 - j1 + 1;
                    else
                         if(i!=0 && N[i][j1] > N[i-1][j1]) a[t][j1][j1] = a[1-t][j1][j1] + 1;
                         else a[t][j1][j1] = 1;

难得的一次过啊。。。经典的01背包问题，那句注释是重点

#include <iostream>
#include <cstring>

#define max(a, b) ( a > b ? a: b)

using namespace std;

//store the max price with weight no more than a[i]
int a[31];

void the_case()
{
    memset(a, 0, sizeof(a));
    int num, p, w, maxw;
    cin >> num;
    while(num--)
    {
        cin >> p >> w;
        for (int i=30; i>=w; i--)//注意是倒序，从没更新的数据实现更新
        {
            a[i] = max(a[i-w]+p, a[i]);
        }
    }
    cin >> num;
    int ans=0;
    while(num--)
    {
        cin >> maxw;
        ans += a[maxw];
    }
        cout << ans << endl;
}

int main()
{
    int c;
    cin >> c;
    while(c--)
    {
        the_case();
    }
}

http://www.algorithmist.com/index.php/Dynamic_Programming

To avoid calculate the same thing again and again, we save the results and return them later. This is commonly known as memorization (记忆）.

There are two types of solution: Bottom Up & Up Bottom.

In general, DP generates all enumerations（枚举）, or rather, the smaller breakdown problems, leading towards the larger cases, they eventually lead towards the final enumeration of size n.

Usage:
S1. check if DP is applicable to the problem
S2. recognize the recursive relationshop, whether it is straightforward or hidden, have a pretty good idea of the relationship

Hallmarks:
#1 Optimal substructure:
      an optimal solution to a problem(instance) contains optimal solution to subproblems.
#2 Overlapping subproblem:
      a recursive solution contains a small number of distinct subproblems repeated many times

This is my first dynamic programming problem solved by myself from beginning to end...

http://www.algorithmist.com/index.php/UVa_11450

该链接指向此类问题的系统解法

Summary

Given a money M (<= 200) and a list of garments C (<= 20). Each garment has K (<= 20) models. You want to buy one model for each garment and you want to spend your money as much as possible.

Explanation

这是“分组背包”的变体——共C组，每组有K个价格不同物品，每组必选一个物品，求不超过已知数据M的最后总价。

My solution（p.s. 拼搏了整整一天的说，还因为各中bug导致怀疑算法遗漏了什么重要部分T T)

使用滚动数组，F0[left0...M]是已经在处理k-1组时更新完毕的数据，left0标记此时总价最小值（因为每组必选一件）

对于F1，使用left1标记该组最小价值，遍历该组所有物品后将left1加至left0，且将F1全部复制给F0后，F1清零。

F1的遍历从当前输入价格p入手，遍历m = left0+p -> M， F1[m] = max( F0[m-p]+p, F1[m] )

这里的意思是，因为F1中存的是K组加上可能的p后的价格，通过max保证了F1在不超过m的条件下存了最大的价值，又因为F0[0...left0]已经失效，所以从left0+p开始考虑，所以从K组遍历的角度来说状态转移方程是F1[m] = max { F0[m-p_i]+p_i } ( i=1..k )。

综上最终答案是F0[20]，若F0[20]==0，说明left0>M，即总价最低已超过已知数据M，若不为0，则输出。

Implementations

#include <iostream>

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

using namespace std;

void the_case()
{
    int M, C, K, p;
    cin >> M >> C;
    int F0 [M+1]; for (int i=0; i<M+1; i++) F0[i]=0;
    int F1 [M+1]; for (int i=0; i<M+1; i++) F1[i]=0;
    int left0 = 0;
    for(int i=0; i<C; i++)
    {
        cin >> K;
        int left1 = M;
        for(int j=0; j<K; j++)
        {
            cin >> p;
            left1 = min(left1, p);
            for(int m=p+left0; m<M+1; m++)
            {
                F1[m] = max(F0[m-p]+p,F1[m]);
            }
        }
        left0 += left1;
        for(int l=0; l<M+1; l++) F0[l]=F1[l];
        for (int l=0; l<M+1; l++) F1[l]=0;
    }  
    if (F0[M]==0) cout << "no solution" << endl;
    else cout << F0[M] << endl;
}      
       
int main()
{
    int N;
    cin >> N;
    while(N--)
    {
        the_case();
    }
    return 0;
}