/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法导论》15.4 最长公共自序列(LCS)
*/
 
#include <iostream>
using namespace std;
 
char b[20][20];
int c[20][20];
 
char x[20], y[20];
 
void LCS()
{
	int m = strlen(x+1);
	int n = strlen(y+1);
 
	for(int i=1; i<=m; ++i)
		c[i][0] = 0;
	for(int j=1; j<=n; ++j)
		c[0][j] = 0;
 
	for(int i=1; i<=m; ++i)
		for(int j=1; j<=n; ++j)
		{
			if(x[i] == y[j])
			{
				c[i][j] = c[i-1][j-1] + 1;
				b[i][j] = '\\';    // 注意这里第一个\\是转移字符，代表\
			}
			else if(c[i-1][j] >= c[i][j-1])
			{
				c[i][j] = c[i-1][j];
				b[i][j] = '|';
			}
			else
			{
				c[i][j] = c[i][j-1];
				b[i][j] = '-';
			}
		}
}
 
void printLCS(int i, int j)
{
	if(i == 0 || j == 0)
		return;
	if(b[i][j] == '\\')
	{
		printLCS(i-1, j-1);
		cout << x[i] << " ";
	}
	else if(b[i][j] == '|')
		printLCS(i-1, j);
	else
		printLCS(i, j-1);
}
 
int main()
{
	cout << "Input the array A:\n";
	cin >> x+1;
	cout << "Input the array B:\n";
	cin >> y+1;
	LCS();
	printLCS(strlen(x+1), strlen(y+1));
}

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
About:  《算法导论》15.1 装配线调度
*/
#include <iostream>
using namespace std;
 
int n;                 // 一个装配线上有n个装配站
int e1, e2;            // 进入装配线1,2需要的时间
int x1, x2;            // 离开装配线1,2需要的时间
int t[3][100];         // t[1][j]表示底盘从S[1][j]移动到S[2][j+1]所需时间,同理t[2][j]
int a[3][100];         // a[1][j]表示在装配站S[1][j]所需时间
int f1[100], f2[100];  // f1[j], f2[j]分别表示在第一/第二条装配线上第j个装配站的最优解
int ln1[100], ln2[100];// ln1[j]记录第一条装配线上,最优解时第j个装配站的前一个装配站是第一条线还是第二条线上
int f, ln;             // 最优解是,f代表最小花费时间，ln表示最后出来时是从装配线1还是装配线2
 
void DP()
{
	f1[1] = e1 + a[1][1];
	f2[1] = e2 + a[2][1];
	for(int j=2; j<=n; ++j)
	{
		// 处理第一条装配线的最优子结构
		if(f1[j-1] + a[1][j] <= f2[j-1] + t[2][j-1] + a[1][j])
		{
			f1[j] = f1[j-1] + a[1][j];
			ln1[j] = 1;
		}
		else
		{
			f1[j] = f2[j-1] + t[2][j-1] + a[1][j];
			ln1[j] = 2;
		}
		// 处理第二条装配线的最优子结构
		if(f2[j-1] + a[2][j] <= f1[j-1] + t[1][j-1] + a[2][j])
		{
			f2[j] = f2[j-1] + a[2][j];
			ln2[j] = 2;
		}
		else
		{
			f2[j] = f1[j-1] + t[1][j-1] + a[2][j];
			ln2[j] = 1;
		}
	}
	if(f1[n] + x1 <= f2[n] + x2)
	{
		f = f1[n] + x1;
		ln = 1;
	}
	else
	{
		f = f2[n] + x2;
		ln = 2;
	}
}
 
void PrintStation()
{
	int i= ln;
	cout << "line " << i << ", station " << n << endl;
	for(int j=n; j>=2; --j)
	{
		if(i == 1)
			i = ln1[j];
		else
			i = ln2[j];
		cout << "line " << i << ", station " << j-1 << endl;
	}
}
 
int main()
{
	//freopen("input.txt", "r", stdin);
	cout << "输入装配站的个数: ";
	cin >> n;
	cout << "输入进入装配线1，2所需的时间e1, e2 :";
	cin >> e1 >> e2;
	cout << "输入离开装配线1, 2所需的时间x1, x2: ";
	cin >> x1 >> x2;
	cout << "输入装配线1上各站加工所需时间a[1][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[1][i];
	cout << "输入装配线2上各站加工所需时间a[2][j]: ";
	for(int i=1; i<=n; ++i)
		cin >> a[2][i];
	cout << "输入装配线1上的站到装配线2上的站所需时间t[1][j]: ";
	//注意这里是i<n，不是i<=n
	for(int i=1; i<n; ++i)
		cin >> t[1][i];
	cout << "输入装配线2上的站到装配线1上的站所需时间t[2][j]: ";
	for(int i=1; i<n; ++i)
		cin >> t[2][i];
	DP();
	cout << "最快需要时间: " << f << endl;
	cout << "路线是: " << endl;
	PrintStation();
	cout << endl;
}

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
Description: 动态规划之三角形求值问题
*/
#include <iostream>
using namespace std;
 
int map[6][6] = 
{
	{0, 0, 0, 0, 0, 0},
	{0, 7, 0, 0, 0, 0},
	{0, 3, 8, 0, 0, 0},
	{0, 8, 1, 0, 0, 0},
	{0, 2, 7, 4, 4, 0},
	{0, 4, 5, 2, 6, 5}
};
 
int f[6][6];
 
int _max(int a, int b)
{
	if(a >= b)
		return a;
	return b;
}
 
int main()
{
	memset(f, 0, sizeof(f));
	for(int i=0; i<6; ++i)
		f[5][i] = map[5][i];
	for(int i=4; i>=1; --i)
		for(int j=1; j<=i; ++j)
			f[i][j] = _max(f[i+1][j], f[i+1][j+1]) + map[i][j];
	for(int i=1; i<=5; ++i)
	{
		for(int j=1; j<=5; ++j)
		{
			cout.width(2);
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	cout << f[1][1] << endl;
}

void RBTreeInsert(RBTree &T, int k)
            {
            //T->parent->color = BLACK;
            Node *y = NULL;
            Node *x = T;
            Node *z = new Node;
            z->key = k;
            z->lchild = z->parent = z->rchild = NULL;
             
            while(x != NULL)
            {
            y = x;
             
            if(k < x->key)
            x = x->lchild;
            else
            x = x->rchild;
            }
             
            z->parent = y;
            if(y == NULL)
            {
            T = z;
            T->parent = NULL;
            T->parent->color = BLACK;
            }
            else
            if(k < y->key)
            y->lchild = z;
            else
            y->rchild = z;
            z->lchild = NULL;
            z->rchild = NULL;
            z->color = RED;
            RBInsertFixup(T, z);
            }

void RBInsertFixup(RBTree &T, Node *z)
            {
            while(z->parent->color == RED)
            {
            if(z->parent == z->parent->parent->lchild)
            {
            Node *y = z->parent->parent->rchild;
            //////////// Case1 //////////////
            if(y->color == RED)
            {
            z->parent->color = BLACK;
            y->color = BLACK;
            z->parent->parent->color = RED;
            z = z->parent->parent;
            }
            else
            {
            ////////////// Case 2 //////////////
            if(z == z->parent->rchild)
            {
            z = z->parent;
            LeftRotate(T, z);
            }
            ////////////// Case 3 //////////////
            z->parent->color = BLACK;
            z->parent->parent->color = RED;
            RightRotate(T, z->parent->parent);
            }
            }
            else
            {
            ///////////////////////
            }
            }
            T->color = BLACK;
            }

void RBInsertFixup(RBTree &T, Node *z)
            {
            while(z->parent->color == RED)
            {
            if(z->parent == z->parent->parent->lchild)
            {
            Node *y = z->parent->parent->rchild;
            //////////// Case1 //////////////
            if(y->color == RED)
            {
            z->parent->color = BLACK;
            y->color = BLACK;
            z->parent->parent->color = RED;
            z = z->parent->parent;
            }
            else
            {
            ////////////// Case 2 //////////////
            if(z == z->parent->rchild)
            {
            z = z->parent;
            LeftRotate(T, z);
            }
            ////////////// Case 3 //////////////
            z->parent->color = BLACK;
            z->parent->parent->color = RED;
            RightRotate(T, z->parent->parent);
            }
            }
            else
            {
            Node *y = z->parent->parent->lchild;
            if(y->color == RED)
            {
            z->parent->color = BLACK;
            y->color = BLACK;
            z->parent->parent->color = RED;
            z = z->parent->parent;
            }
            else
            {
            if(z == z->parent->lchild)
            {
            z = z->parent;
            RightRotate(T, z);
            }
            z->parent->color = BLACK;
            z->parent->parent->color = RED;
            LeftRotate(T, z->parent->parent);
            }
            }
            }
            T->color = BLACK;
            }
             
            void RBTreeInsert(RBTree &T, int k)
            {
            //T->parent->color = BLACK;
            Node *y = NULL;
            Node *x = T;
            Node *z = new Node;
            z->key = k;
            z->lchild = z->parent = z->rchild = NULL;
             
            while(x != NULL)
            {
            y = x;
             
            if(k < x->key)
            x = x->lchild;
            else
            x = x->rchild;
            }
             
            z->parent = y;
            if(y == NULL)
            {
            T = z;
            T->parent = NULL;
            T->parent->color = BLACK;
            }
            else
            if(k < y->key)
            y->lchild = z;
            else
            y->rchild = z;
            z->lchild = NULL;
            z->rchild = NULL;
            z->color = RED;
            RBInsertFixup(T, z);
            }