Gun's Blog

算法导论

Word count: 433Reading time: 2 min
2019/08/29 Share

emmm,我太难了,最后还是没能写对,自己的思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/*
3 2
A 10 100
B 5 50
C 100 5
ACB
ABC
*/
#include<iostream>
#include<string.h>
using namespace std;
void matrixChain(int* p, int **m,int n);
void QuickSort(int array[], int start, int last);
int len(char[]);
int main() {
int n, m;
while (cin >> n >> m)
{
char chain[101];
int row[10], colum[10];
int* p = new int[n], * mansion, * cal;
mansion = p + 1;
cal = p;
int answer;
int** matrix = { 0 };
for (int i = 0; i < n; i++)
{
cin >> chain[i] >> row[i] >> colum[i];
}
char test[3][101];
for (int i = 0; i < m; i++)
{
cin >> test[i];

for (int i = 0; test[i] != '\0'; i++)
{
for (int j = 0; j <= len(chain); j++)
{
if (test[i][j] == chain[j])
{
*p = row[j];
*(++p) = colum[j];
}
}
}
for (int i = 0; i < n; i++)
{
if (*mansion != *(++mansion)) {
cout << "MengMengDa" << endl;
return 0;
}
mansion++;
}
matrixChain(cal, matrix, n);
}
}
return 0;
}
void matrixChain(int* p, int **m, int n)
{
for (int i = 1; i <= n; i++)
{
m[i][i] = 0;
}
for (int i = n - 1; i <= 1; i--)
{
for (int j = i + 1; j <= n; j++)
{
int* temp = new int[j - i];
for (int k = i; k < j; k++)
{
*temp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
temp++;
}
QuickSort(temp, 0, j - i);
m[i][j] = temp[0];
}
}
cout << m[1][n] << endl;
}
void QuickSort(int array[], int start, int last)
{
int i = start;
int j = last;
int temp = array[i];
if (i < j)
{
while (i < j)
{
//
while (i < j && array[j] >= temp)
j--;
if (i < j)
{
array[i] = array[j];
i++;
}

while (i < j && temp > array[i])
i++;
if (i < j)
{
array[j] = array[i];
j--;
}

}
array[i] = temp;
QuickSort(array, start, i - 1);
QuickSort(array, i + 1, last);
}
}
int len(char chain[])
{
int i = 0;
for ( i = 0; chain[i] != '\0'; i++)
{
i++;
}
return i;
}

可能最后即使调对了,也实践超限了吧…

CATALOG