完成程序1.有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。游戏第1步,将一条边删除。随后n-1步按以下方式操作: (1)选择一条边E以及由E连接着的2个顶点V1和V2; (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。新顶点的值为顶点V1和V2的整数值通过边E上的运算得到的值。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。 要求:给出节点数n,并按顺序给出n个整数值和运算符号,输出最高得分以及最高得分的计算顺序
时间: 2023-06-11 16:08:18 浏览: 41
这是一个典型的动态规划问题。我们可以用dp[i][j]表示从第i个点到第j个点所能得到的最大值,其中i和j之间的边已经被删除。然后我们需要枚举最后一条被删除的边,假设它连接了第k个点和第k+1个点,那么我们可以将其拆分为两个子问题:dp[i][k]和dp[k+1][j],然后将它们的结果相加,再加上第k个点和第k+1个点通过这条边得到的值,即val[k][k+1](val[i][j]表示第i个点和第j个点通过边上的运算得到的值)。
因此,我们可以得到状态转移方程:
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + val[k][k+1])
注意,我们需要先枚举较小的区间长度len,再枚举左端点i,然后计算右端点j。最终的答案即为dp[1][n]。
同时,我们需要记录转移时的决策,即最后一条被删除的边,可以用pre[i][j]表示从第i个点到第j个点所能得到的最大值的决策,即最后一条被删除的边连接的两个点。在转移时更新pre[i][j]即可。
以下是代码实现:
相关问题
用动态规划wancheng程序1.有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。游戏第1步,将一条边删除。随后n-1步按以下方式操作: (1)选择一条边E以及由E连接着的2个顶点V1和V2; (2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。新顶点的值为顶点V1和V2的整数值通过边E上的运算得到的值。 最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。
这道题可以用动态规划来解决。我们定义 $f_{i,j,0/1}$ 表示将区间 $[i,j]$ 合并起来得到的最大/最小值,其中 $0$ 表示最大值,$1$ 表示最小值。同时,我们在原序列两端各加入一个数,令 $a_0=a_n=1$,这样就可以将多边形变成一个环。
根据动态规划的思想,我们考虑将问题划分成若干个子问题,然后利用子问题的结果推导出原问题的结果。我们可以枚举区间 $[i,j]$ 中最后一条被删除的边的位置 $k$,那么就可以将原问题划分成两个子问题,即将区间 $[i,k]$ 和 $[k,j]$ 分别合并起来,然后再用边 $k$ 的运算符合并这两个子问题。具体地,我们有以下状态转移方程:
$$
\begin{aligned}
f_{i,j,0}&=\max_{i\leq k<j}(f_{i,k,0}\ \text{运算符}\ f_{k+1,j,0})\ \text{或}\ \max_{i\leq k<j}(f_{i,k,1}\ \text{运算符}\ f_{k+1,j,1})\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(对应的运算符为“+”)}\\
f_{i,j,1}&=\min_{i\leq k<j}(f_{i,k,0}\ \text{运算符}\ f_{k+1,j,0})\ \text{或}\ \min_{i\leq k<j}(f_{i,k,1}\ \text{运算符}\ f_{k+1,j,1})\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(对应的运算符为“*”)}
\end{aligned}
$$
初始状态为 $f_{i,i,0}=f_{i,i,1}=a_i$。最终答案为 $f_{1,n,0}$。
时间复杂度为 $O(n^3)$,可以通过此题。以下是代码实现:
用c语言写一个求有向图中每个顶点的入度和出度的程序
好的,以下是一个求有向图中每个顶点入度和出度的 C 语言程序:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100
// 有向图的邻接矩阵表示法结构体
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存储顶点的数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的邻接矩阵
int vertex_num; // 顶点数
int arc_num; // 边数
} Graph;
// 初始化有向图
void init_graph(Graph *G) {
int i, j;
printf("请输入顶点数和边数:");
scanf("%d %d", &G->vertex_num, &G->arc_num);
printf("请输入顶点信息:");
for (i = 0; i < G->vertex_num; i++) {
scanf("%d", &G->vertex[i]);
}
for (i = 0; i < G->vertex_num; i++) {
for (j = 0; j < G->vertex_num; j++) {
G->arc[i][j] = 0; // 初始化邻接矩阵
}
}
printf("请输入每条边的起点和终点:\n");
for (i = 0; i < G->arc_num; i++) {
int start, end;
scanf("%d %d", &start, &end);
G->arc[start][end] = 1; // 构建邻接矩阵
}
}
// 计算有向图每个顶点的入度和出度
void calc_degree(Graph *G, int indegree[], int outdegree[]) {
int i, j;
for (i = 0; i < G->vertex_num; i++) {
indegree[i] = 0;
outdegree[i] = 0;
for (j = 0; j < G->vertex_num; j++) {
if (G->arc[i][j] == 1) {
outdegree[i]++;
indegree[j]++;
}
}
}
}
// 输出有向图每个顶点的入度和出度
void print_degree(Graph *G, int indegree[], int outdegree[]) {
int i;
printf("顶点\t入度\t出度\n");
for (i = 0; i < G->vertex_num; i++) {
printf("%d\t%d\t%d\n", G->vertex[i], indegree[i], outdegree[i]);
}
}
int main() {
Graph G;
int indegree[MAX_VERTEX_NUM], outdegree[MAX_VERTEX_NUM]; // 存储每个顶点的入度和出度
init_graph(&G); // 初始化有向图
calc_degree(&G, indegree, outdegree); // 计算每个顶点的入度和出度
print_degree(&G, indegree, outdegree); // 输出每个顶点的入度和出度
return 0;
}
```
程序的主要思路是:
1. 定义一个结构体 `Graph`,用邻接矩阵的方式表示有向图;
2. 初始化有向图,包括输入顶点数、边数、顶点信息和每条边的起点和终点,构建邻接矩阵;
3. 计算每个顶点的入度和出度,遍历邻接矩阵,统计每个顶点的入度和出度;
4. 输出每个顶点的入度和出度,按照格式输出即可。
以上程序可以计算有向图中每个顶点的入度和出度,可以根据实际需求进行修改。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)