// LongestPublicChildSequence.cpp : 定义控制台应用程序的入口点。

#include "stdafx.h"
/**
最长公共子序列，子序列指元素间顺序不变，但不要求连续的数组元素集合
最长公共子序列，指两个数组共有的子序列中最长的那个一个
分类：动态规划
作者：夏军
时间：2018年5月7日
**/
int getMax(int a,int b) {
	return a>b?a:b;
}

int main()
{
	char x[8] = {'A','B','C','B','A','C','B','A'};
	char y[6] = {'B','D','C','A','B','A'};
	int child[9][7];
	//数组初始化
	for(int i = 0;i < 9;i++) {
		for(int j = 0;j < 7;j++) {
			child[i][j] = 0;
		}
	}
	
	for(int i = 1;i < 9;i++) {
		for(int j = 1;j < 7;j++) {
			if(x[i] == y[j]) {//末尾相同，公共子序列长度加1
				child[i][j] = child[i-1][j-1]+1;
			} else {
				child[i][j] = getMax(child[i-1][j],child[i][j-1]);
			}
		}
	}

	printf("最长公共子序列的长度是：%d",child[8][6]);
	return 0;
}

// MaxValueChildArray.cpp : 定义控制台应用程序的入口点。
/**
最大子数组问题：求一个数组的子数组，要求子数组的元素的和在所有的子数组中最大
时间复杂度O(n)
这个问题调用了两次动态规划，比较难
@author:XiaJun
@date May 6th,2018
**/

#include "stdafx.h"


int main()
{
	int arr[11] = {-2,6,5,-9,1,-3,9,12,-23,18,2};
	//以边界为终点的最大子数组和要求的最大子数组
	int bound[11],result[11];
	//初始化
	int i = 0,j = 0;
	for(i = 0;i < 11;i++) {
		bound[i] = 0;
		result[i] = 0;
	}
	//利用动态规划求边界为终点(当前的遍历索引在子数组的边界)的最大子数组
	int curMax = arr[0];
	bound[0] = arr[0];
	for(i = 1;i < 11;i++) {
		if(curMax <= 0) {
			curMax = arr[i];
		} else {
			curMax += arr[i];
		}
		bound[i] = curMax;
	}
	//求最终的最大子数组
	int maxValue = arr[0];
	result[0] = arr[0];
	for(i = 1;i < 11;i++) {
		if(arr[i] > 0) {//小于0不用考虑，这种情况下最大子数组的和不变
			if(arr[i]+bound[i-1] > maxValue) {
				maxValue = arr[i]+bound[i-1];//该元素被包含在了最大子数组中
			}
		}
	}
	printf("最大子数组的和是：%d\n",maxValue);
	return 0;
}

// Matrix.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

/**
矩阵的乘法链问题：多个矩阵相乘时，怎么加括号，总的乘法次数最小
比如3个矩阵相乘，可以先计算前两个的积，再乘以第三个，也可以先计算后两个的积
再乘以第一个。两种方法的乘法次数不同。
来源：《算法导论》第四版中文版P205
分类：动态规划，算法，ACM
@Author:XiaJun
@Time:May 5th,2018
**/

int main()
{
	//6个矩阵，行数和列数
	int mat[6][2] = {{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};

	//一个5行5列的矩阵，记录最优子结构的值
	int child[6][6];
	int i,j,dis,k = 0,min;
	//初始化该矩阵
	for(i = 0;i < 6;i++) {
		for(j = 0;j < 6;j++) {
			child[i][j] = 0;
		}
	}

	//两个矩阵相乘的最优子结构的值是已知的
	for(i = 0;i < 5;i++) {
		child[i][i+1] = mat[i][0]*mat[i][1]*mat[i+1][1];
	}

	//计算所有的最优子结构
	for(dis = 2;dis < 6;dis++) {
		for(i = 0;dis+i < 6;i++) {//i：最优子结构的起始处
			j = i+dis;//j：最优子结构的结束处
			min = mat[i][0]*mat[i][1]*mat[j][1]+mat[i+1][j];
			for(k = i;k < j;k++) {
				int cur = mat[i][0]*mat[k][1]*mat[j][1]+child[i][k]+child[k+1][j];
				min = min > cur?cur:min;
			}
			child[i][j] = min;
		}
	}

	printf("最少的乘法计算次数是：%d",child[0][5]);

	return 0;
}

// AssembleLineProblem.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

/**
装配线问题，装配线2条，装配站6个
来源：《算法导论》第四版中文版P192
分类：动态规划，算法，ACM
@Author:XiaJun
@Time:May 3rd,2018
**/

//在装配线上装配的时间
int assembleTime[2][6] = {{7,9,3,4,8,4},{8,5,6,4,5,7}};

//转移的时间
int transTime[2][6] = {{2,2,1,2,2,1},{4,2,3,1,3,4}};

//最后一道流程装配完成后到下线的时间
int offLineTime[2][1] = {{3},{2}};

//求最小值
int getMin(int a,int b) {
	return a < b?a:b;
}

int main()
{
	//存放到达第几个装配站的最短时间，f[1][1]表示到达第2条装配线的第2个装配站的最短时间
	int fast[2][6];
	//初始化，C语言这一点很蛋疼
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 6;j++)
			fast[i][j] = 0;
	//初始化装配站1的最短时间
	fast[0][0] = transTime[0][0]+assembleTime[0][0];
	fast[1][0] = transTime[1][0]+assembleTime[1][0];

	//开始计算
	for(int j = 1;j < 6;j++) {
		//从同一条生产线直接投送过来所需的时间
		int sameLine = fast[0][j-1]+assembleTime[0][j];
		//从另一条生产线转移过来所需的时间
		int otherLine = fast[1][j-1]+assembleTime[0][j]+transTime[0][j];
		fast[0][j] = getMin(sameLine,otherLine);

		//从同一条生产线直接投送过来所需的时间
		sameLine = fast[1][j-1]+assembleTime[1][j];
		//从另一条生产线转移过来所需的时间
		otherLine = fast[0][j-1]+assembleTime[1][j]+transTime[1][j];
		fast[1][j] = getMin(sameLine,otherLine);
	}

	//最终的结果
	int result = getMin(fast[0][5]+offLineTime[0][0],fast[1][5]+offLineTime[1][0]);
    printf("最短的装配时间：%d",result);
	return 0;
}