BabbleDay's Blog

S1 make Arch 64 compatible with lib32: install lib32-* from [multilib]

# vim /etc/pacman.conf

    => [multilib]

    SigLevel = PackageRequired

    Include = /etc/pacman.d/mirrorlist

# pacman -Syu ---- update multilib to local database

S2 install android_sdk

# pacman -S android-sdk android-sdk-platform-tools android-sdk-build-tools

[Alt + F2] android ---- run Android SDK Manager

    => makesure the following:

     Underneath “Tools”, check the box for “Android SDK Platform-tools”. (The “Android SDK Tools” item will already be installed.)
     Beneath “Android 2.3.3 (API 10)”, select “SDK Platform”. (As of Processing 2.0b7, you no longer need to include the “Google APIs” item.)

S3 lauch Processing and add ''Android Mode'' to Processing

    If there is a warning about missing ANDROID_SDK variable,
   choose 'yes' (installed sdk) and choose the directory '' / → opt → android_sdk ''

S4 write the simple program and run it on ur phone

        void setup(){}
        void draw(){  background(0);  rect(mouseX, mouseY, 100, 100);  }

竟然因为使用滚动数组是不小心把1-t写成t-1而debug半个多小时。。。。下次一定要注意。。。。

oj数据输入技巧：若没有输入结束标志，则可使用返回布尔值的init（）来控制输入结束

bool init()
{
    getline(cin, str1);
    m = str1.length();
    if(m==0) return false;
    getline(cin, str2);
    n = str2.length();
    return true;
}

只求子序列的长度的算法：
设str1[1,2,3...m] str2[1,2,3...n]
a[t][m] t是滚动数组标志，遍历str2的所有作为行i
             m是str1的所有，作为列j
所以 a[t][j] = a[1-t][j-1] + 1 when str1[i] == str2[j]
                       max { a[1-t][j] , a[t][j-1] } otherwise

#include <iostream>
#include <string>
#include <cstring>
#define max(a, b) a>b?a:b

using namespace std;

string str1;
string str2;
int m=0;
int n=0;

bool init()
{
    getline(cin, str1);
    m = str1.length();
    if(m==0) return false;
    getline(cin, str2);
    n = str2.length();
    return true;
}

void the_case()
{
    int a[2][m+1];
    memset(a, 0, sizeof(a));
    int t=0;
    for(int i=0; i<n; i++)
    {
        memset(a[t], 0, sizeof(a[t]));
        for(int j=1; j<m+1; j++)
        {
            if(str1.at(j-1) == str2.at(i))
                a[t][j] = a[1-t][j-1] + 1;
            else
                a[t][j] = max( a[t][j-1], a[1-t][j] );
        }
        t = 1-t;
    }
    cout << a[1-t][m] << endl;
}

int main()
{
    while(init())
    {
        the_case();
    }
    return 0;
}

关于使用回溯法重构子序列，有待更新

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();
    }
}

两句话：不要轻易使用模拟编程，算下时间复杂度。“一左一右”之类的联想二进制，学会利用二进制的移位操作。。。

这是模拟过程的代码，可惜超时了

#include <iostream>
#include <cmath>

using namespace std;

void the_case()
{
    int depth, num;
    cin >> depth;
    num = pow(2, depth);
    bool node[num];
    for (int i=0; i<num; i++) node[i] = false;

    int n, r;
    cin >> n;
   for(int k=1; k<=n; k++) 
    {
        int j=1;
        for (int i=1; i<depth; i++)
        {
            if (node[j]==false)
            {
                node[j]=true;
                j = j * 2;
            }
            else 
            {
                node[j]=false;
                j = j*2 +1;
            }
        }
        r = j;
    }
    cout << r << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        the_case();
    }
    cin.clear();
    return 0;
}

后来很郁闷的从前辈那边学到了算法：观察第i个球与最后位置p的数学关系发现“p的二进制做镜像后和2×i+1的二进制一样”

补充下思考细节，因为对于叶子节点的二进制来说，最高位每两次一循环（01），次高位每4次一循环（0011），次次高位每8位一循环（00001111），就会发现和二进制计数递增数列成镜像

#include <iostream>

using namespace std;

void the_case()
{
    int depth, no;
    unsigned int m; //注意使用unsigned在这种移位操作中
    cin >> depth >> no;
    unsigned int t=0; //同上
    m = no*2-1; //第no个变成2×no+1
    while(depth--) //数的深度等于二进制位数
    {
        t <<= 1; //将t已有位数左移保留
        t += m&1; //这里是提取出m的最低位
        m >>= 1; //将m已经镜像的位数移去
    }
    cout << t << endl;
}

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

向前辈表示敬意和感谢，对自己继续勉励！！

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;
}