GXUOJ-算法-第二次作业

1.矩阵连（链）乘

题目描述

GXUOJ | 矩阵连乘

代码解答

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N=50;
5. int m[N][N];
6. int p[N];
7. int n;
9. int main(){
10.         cin>>n;
11.        
12.     //m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。
13.         for(int i=0;i<=n;i++){
14.                 cin>>p[i];
15.                 m[i][i]=0;
16.         }
17.        
18.         for(int r=2;r<=n;r++){
19.                 for(int i=1;i<=n-r+1;i++){
20.                        
21.                        
22.                         int j=r+i-1;
23.                         //初始化， m[i][j] 相当于 Ai，Ai+1···Aj 的最小乘积,       
24.                         //m[i+1][j]是A【i+1]到A[j]的最小乘积
25.                         m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
27.                         //k=i+1/i  k<=j/k<j 四个结合都没有影响
28.                         for(int k=i+1;k<j;k++){
29.                                 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
30.                                 if(t<m[i][j])
31.                                         m[i][j]=t;
32.                         }
33.                 }
34.         }
35.         cout<<m[1][n];
36. }

复制代码

解题思绪

   i代表开始的下标，j代表结束的下标，r代表矩阵的长度。
  m[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)

代码解答

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main(){
5.         string text1,text2;
6.         cin>>text1>>text2;
7.         int len1=text1.length();
8.         int len2=text2.length();
9.         //这两个都可以
10.         //int len1=text1.size();
11.         //int len2=text2.size();
12.         int dp[1000][1000]={0};
13.        
14.         for(int i=0;i<len1;i++){
15.                 for(int j=0;j<len2;j++){
16.                         if(text1[i]==text2[j])
17.                     //当前字符相等时，最长公共子序列长度在之前的基础上加 1
18.                                 dp[i+1][j+1]=dp[i][j]+1;
19.                         else
20.                                 dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
21.                         //这意味着取text1去掉当前字符与text2的最长公共子序列长度
22.                                 //和text2去掉当前字符与text1的最长公共子序列长度中的最大值。
23.        }
24.         }
25.        
26.         cout<<dp[len1][len2];
27.         return 0;
28. }

复制代码

3.0-1背包题目

题目描述

GXUOJ | 0-1背包题目

代码解答

1. #include<bits/stdc++.h>
2. using namespace std;
4. int n,m;
5. const int N=1005;
6. int w[N],v[N],dp[N];
8. int main(){
9.         cin>>n>>m;
10.         for(int i=0;i<n;i++)
11.                 cin>>v[i];
12.         for(int i=0;i<n;i++)
13.                 cin>>w[i];
14.                
15.         for(int i=0;i<n;i++){
16.                 for(int j=m;j>=w[i];j--){
17.                         // 状态转移方程：选择当前物品或不选择当前物品中的较大价值
18.                         dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
19.                 }
20.         }
21.         cout<<dp[m];
22. }

复制代码

4.带权区间调度

题目描述

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

代码解答

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=1005;
4. struct Task{
5.         int start,end,value;
6. }tasks[N];
8. int dp[N];
9. bool compareTask(Task a,Task b){
10.         return a.end<b.end;
11. }
12. int find(int i){
13.         int l=0;int r=i-1;
14.         while(l<=r){
15.                 int mid=(l+r)/2;
16.                 // 如果中间位置任务的结束时间小于等于当前任务i的开始时间
17.         // 说明可能存在更靠后的不冲突任务，调整左边界
18.                 if(tasks[mid].end<=tasks[i].start)
19.                         l=mid+1;
20.                 else
21.                         r=mid-1;
22.         }
23.         return r;
24. }
25. int main(){
26.         int n;cin>>n;
27.         for(int i=0;i<n;i++)
28.                 cin>>tasks[i].start>>tasks[i].end>>tasks[i].value;
29.        
30.         sort(tasks,tasks+n,compareTask);
31.        
32.         for(int i=0;i<n;i++){
33.                 int x=find(i);
34.                 dp[i+1]=max(dp[i],dp[x+1]+tasks[i].value);
35.         }
36.         cout<<dp[n];
37.         return 0;
38. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。