GXUOJ-算法-第二次作业（矩阵连乘、最长公共子序列、0-1背包问题、带权区间调度）

1.矩阵连（链）乘

问题描述

GXUOJ | 矩阵连乘

代码解答

#include<bits/stdc++.h>
using namespace std;

const int N=50;
int m[N][N];
int p[N];
int n;

int main(){
	cin>>n;
	
    //m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。
	for(int i=0;i<=n;i++){
		cin>>p[i];
		m[i][i]=0;
	}
	
	for(int r=2;r<=n;r++){
		for(int i=1;i<=n-r+1;i++){
			
			
			int j=r+i-1;
			//初始化， m[i][j] 相当于 Ai，Ai+1···Aj 的最小乘积,	
			//m[i+1][j]是A【i+1]到A[j]的最小乘积 
			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];

			//k=i+1/i  k<=j/k<j 四个结合都没有影响 
			for(int k=i+1;k<j;k++){
				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
				if(t<m[i][j])
					m[i][j]=t;
			}
		}
	}
	cout<<m[1][n];
}

解题思路

i代表开始的下标，j代表结束的下标，r代表矩阵的长度。

m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。

当我们计算（Ai*···*Ak）和(Ak*···Aj)这两个子矩阵链乘结果相乘时，
就相当于计算两个矩阵相乘，其中第一个子矩阵链乘结果是
p[i-1]*p[k]一个的矩阵，第二个子矩阵链乘结果是p[k]*p[j]一个的矩阵。
根据矩阵乘法运算量的计算公式，这两个子矩阵链乘结果相乘所需的乘法次数就是
p[i - 1] * p[k] * p[j]。

2.最长公共子序列（LCS）

问题描述

GXUOJ | 最长公共子序列(LCS)

代码解答

#include<bits/stdc++.h>
using namespace std;

int main(){
	string text1,text2;
	cin>>text1>>text2;
	int len1=text1.length();
	int len2=text2.length();
	//这两个都可以 
	//int len1=text1.size();
	//int len2=text2.size();
	int dp[1000][1000]={0};
	
	for(int i=0;i<len1;i++){
		for(int j=0;j<len2;j++){
			if(text1[i]==text2[j])
	            //当前字符相等时，最长公共子序列长度在之前的基础上加 1
				dp[i+1][j+1]=dp[i][j]+1;
			else
				dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
		        //这意味着取text1去掉当前字符与text2的最长公共子序列长度
				//和text2去掉当前字符与text1的最长公共子序列长度中的最大值。
       }
	}
	
	cout<<dp[len1][len2];
	return 0;
}

3.0-1背包问题

问题描述

GXUOJ | 0-1背包问题

代码解答

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N=1005;
int w[N],v[N],dp[N];

int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>v[i];
	for(int i=0;i<n;i++)
		cin>>w[i];
		
	for(int i=0;i<n;i++){
		for(int j=m;j>=w[i];j--){
			// 状态转移方程：选择当前物品或不选择当前物品中的较大价值
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[m];
}

4.带权区间调度

问题描述

GXUOJ | 带权区间调度（Weighted Interval Scheduling）

代码解答

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct Task{
	int start,end,value;
}tasks[N];

int dp[N];
bool compareTask(Task a,Task b){
	return a.end<b.end;
}
int find(int i){
	int l=0;int r=i-1;
	while(l<=r){
		int mid=(l+r)/2;
		// 如果中间位置任务的结束时间小于等于当前任务i的开始时间
        // 说明可能存在更靠后的不冲突任务，调整左边界
		if(tasks[mid].end<=tasks[i].start)
			l=mid+1;
		else
			r=mid-1;
	}
	return r;
}
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++)
		cin>>tasks[i].start>>tasks[i].end>>tasks[i].value;
	
	sort(tasks,tasks+n,compareTask);
	
	for(int i=0;i<n;i++){
		int x=find(i);
        //dp[x + 1]代表的是在任务i之前且与任务i兼容（不冲突）的任务中，
		//能够获得的最大价值。
		dp[i+1]=max(dp[i],dp[x+1]+tasks[i].value);
	}
	cout<<dp[n];
	return 0;
}