GXUOJ-算法-第二次作业
1.矩阵连（链）乘题目描述
GXUOJ | 矩阵连乘
https://i-blog.csdnimg.cn/direct/c4e65c5357f34478a6309eae5aa4fa51.png
代码解答
#include<bits/stdc++.h>
using namespace std;
const int N=50;
int m;
int p;
int n;
int main(){
cin>>n;
//m 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。
for(int i=0;i<=n;i++){
cin>>p;
m=0;
}
for(int r=2;r<=n;r++){
for(int i=1;i<=n-r+1;i++){
int j=r+i-1;
//初始化， m 相当于 Ai，Ai+1···Aj 的最小乘积,
//m是A【i+1]到A的最小乘积
m=m+p*p*p;
//k=i+1/ik<=j/k<j 四个结合都没有影响
for(int k=i+1;k<j;k++){
int t=m+m+p*p*p;
if(t<m)
m=t;
}
}
}
cout<<m;
} 解题思绪
i代表开始的下标，j代表结束的下标，r代表矩阵的长度。
m 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。
当我们计算（Ai*···*Ak）和(Ak*···Aj)这两个子矩阵链乘结果相乘时，
就相当于计算两个矩阵相乘，此中第一个子矩阵链乘结果是
p*p一个的矩阵，第二个子矩阵链乘结果是p*p一个的矩阵。
根据矩阵乘法运算量的计算公式，这两个子矩阵链乘结果相乘所需的乘法次数就是
p * p * p。
2.最长公共子序列（LCS）
题目描述
GXUOJ | 最长公共子序列(LCS)
https://i-blog.csdnimg.cn/direct/126b9dd76cce48bb87fc9df959e1582f.png
代码解答
#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={0};
for(int i=0;i<len1;i++){
for(int j=0;j<len2;j++){
if(text1==text2)
//当前字符相等时，最长公共子序列长度在之前的基础上加 1
dp=dp+1;
else
dp=max(dp,dp);
//这意味着取text1去掉当前字符与text2的最长公共子序列长度
//和text2去掉当前字符与text1的最长公共子序列长度中的最大值。
}
}
cout<<dp;
return 0;
}
3.0-1背包题目
题目描述
GXUOJ | 0-1背包题目
https://i-blog.csdnimg.cn/direct/5b7bebf18f6e46319af9af2fec689958.png
代码解答
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1005;
int w,v,dp;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>v;
for(int i=0;i<n;i++)
cin>>w;
for(int i=0;i<n;i++){
for(int j=m;j>=w;j--){
// 状态转移方程：选择当前物品或不选择当前物品中的较大价值
dp=max(dp,dp]+v);
}
}
cout<<dp;
}
4.带权区间调度
题目描述
GXUOJ | 带权区间调度（Weighted Interval Scheduling）
https://i-blog.csdnimg.cn/direct/9c94b1b6d3d544268d4cd76cf8bca9d3.png
代码解答
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
struct Task{
int start,end,value;
}tasks;
int dp;
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.end<=tasks.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.start>>tasks.end>>tasks.value;
sort(tasks,tasks+n,compareTask);
for(int i=0;i<n;i++){
int x=find(i);
dp=max(dp,dp+tasks.value);
}
cout<<dp;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]