保定做网站电话,机械设备行业网站建设,凡科做的网站,免费网站代理访问1.矩阵连#xff08;链#xff09;乘
问题描述
GXUOJ | 矩阵连乘 代码解答
#includebits/stdc.h
using namespace std;const int N50;
int m[N][N];
int p[N];
int n;int main(){cinn;//m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小…1.矩阵连链乘
问题描述
GXUOJ | 矩阵连乘 代码解答
#includebits/stdc.h
using namespace std;const int N50;
int m[N][N];
int p[N];
int n;int main(){cinn;//m[i][j] 存储的是从第 i 个矩阵到第 j 个矩阵这一段矩阵链相乘的最小计算次数。for(int i0;in;i){cinp[i];m[i][i]0;}for(int r2;rn;r){for(int i1;in-r1;i){int jri-1;//初始化 m[i][j] 相当于 AiAi1···Aj 的最小乘积, //m[i1][j]是A【i1]到A[j]的最小乘积 m[i][j]m[i1][j]p[i-1]*p[i]*p[j];//ki1/i kj/kj 四个结合都没有影响 for(int ki1;kj;k){int tm[i][k]m[k1][j]p[i-1]*p[k]*p[j];if(tm[i][j])m[i][j]t;}}}coutm[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) 代码解答
#includebits/stdc.h
using namespace std;int main(){string text1,text2;cintext1text2;int len1text1.length();int len2text2.length();//这两个都可以 //int len1text1.size();//int len2text2.size();int dp[1000][1000]{0};for(int i0;ilen1;i){for(int j0;jlen2;j){if(text1[i]text2[j])//当前字符相等时最长公共子序列长度在之前的基础上加 1dp[i1][j1]dp[i][j]1;elsedp[i1][j1]max(dp[i][j1],dp[i1][j]);//这意味着取text1去掉当前字符与text2的最长公共子序列长度//和text2去掉当前字符与text1的最长公共子序列长度中的最大值。}}coutdp[len1][len2];return 0;
}3.0-1背包问题
问题描述
GXUOJ | 0-1背包问题 代码解答
#includebits/stdc.h
using namespace std;int n,m;
const int N1005;
int w[N],v[N],dp[N];int main(){cinnm;for(int i0;in;i)cinv[i];for(int i0;in;i)cinw[i];for(int i0;in;i){for(int jm;jw[i];j--){// 状态转移方程选择当前物品或不选择当前物品中的较大价值dp[j]max(dp[j],dp[j-w[i]]v[i]);}}coutdp[m];
} 4.带权区间调度
问题描述
GXUOJ | 带权区间调度Weighted Interval Scheduling 代码解答
#includebits/stdc.h
using namespace std;
const int N1005;
struct Task{int start,end,value;
}tasks[N];int dp[N];
bool compareTask(Task a,Task b){return a.endb.end;
}
int find(int i){int l0;int ri-1;while(lr){int mid(lr)/2;// 如果中间位置任务的结束时间小于等于当前任务i的开始时间// 说明可能存在更靠后的不冲突任务调整左边界if(tasks[mid].endtasks[i].start)lmid1;elsermid-1;}return r;
}
int main(){int n;cinn;for(int i0;in;i)cintasks[i].starttasks[i].endtasks[i].value;sort(tasks,tasksn,compareTask);for(int i0;in;i){int xfind(i);dp[i1]max(dp[i],dp[x1]tasks[i].value);}coutdp[n];return 0;
}
