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])//当前字符相等时，最长公共子序列长度在之前的基础上加 1dp[i+1][j+1]=dp[i][j]+1;elsedp[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;elser=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;
}