include iostream include stdlib include stdio include string include s

  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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <sstream>
#define DEBUG
template <typename T>
class matrix {
private:
T* value = NULL;
int* param = NULL;
int dimension = 0;
inline int GetIndex(int* vector) {
int index = 0;
for (int i = 0; i < dimension; i++) {
index += vector[i] * param[i];
}
return index;
}
public:
matrix(int dim, int* vector): dimension(dim) {
param = new int[dim];
int size = 1;
for (int i = 0; i < dim; i++) {
param[dim - i - 1] = size;
size *= vect[i];
}
value = new T[size];
memset(value, 0, sizeof(T) * size);
}
~matrix() {
if (value) delete [] value;
if (param) delete [] param;
}
T get(int* vector) { return value[GetIndex(vector)]; }
void set(int* vector, T val) { value[GetIndex(vector)] = val; }
};
//Удаление всех пробелов из строки
inline void SpaceErase(std::string &str) {
for(int i = 0; i < str.length(); i++) {
if(str[i] == ' ') {
str.erase(i,1);
i--;
}
}
}
bool Check(int* tek_position, int* dim_vector, int n) {
for (int i = 0; i < n; i++) {
if (tek_position[i] < dim_vector[i] - 1) return TRUE;
}
return FALSE;
}
inline void GoTo(int* tek_position, int n, int step_vector) {
for (int i = 0; i < n; i++) {
tek_position[i] += ((step_vector & (1 << i)) > 0);
}
}
inline void GoBack(int* tek_position, int n, int step_vector) {
for (int i = 0; i < n; i++) {
tek_position[i] -= ((step_vector & (1 << i)) > 0);
}
}
int main(int argc, char** argv) {
if (argc < 2) {
std::cout << "Need more arguments!" << std::endl;
return 0;
}
//Входные данные
int n; //число последовательностей
int penalty = -1;
std::string* seq; //последовательности
std::fstream fs;
fs.open (argv[1], std::fstream::in);
fs >> n >> std::ws;
seq = new std::string[n];
for (int i = 0; i < n; i++) {
std::getline(fs, seq[i]);
}
//Чтение алфавита и таблицы очков---------------------------------------------
std::string alphabet;
int index_arr[128];
fs >> std::ws;
std::getline(fs, alphabet);
SpaceErase(alphabet);
for (int i = 0; i < alphabet.length(); i++) {
index_arr[alphabet[i]] = i;
}
int** score_matrix = new int* [alphabet.length()];
for (int i = 0; i < alphabet.length(); i++) {
score_matrix[i] = new int [alphabet.length()];
}
for (int i = 0; i < alphabet.length(); i++) {
for (int j = 0; j < alphabet.length(); j++) {
fs >> score_matrix[i][j];
/*if (i == j) score_matrix[i][j] = 2;
else score_matrix[i][j] = -1;*/
}
}
fs >> penalty;
fs.close();
//Алгоритм====================================================================
int dim_vector[n];
for (int i = 0; i < n; i++) {
dim_vector[i] = seq[i].length() + 1; //добавляем нулевые столбцы
}
matrix<int> calc_matrix(n, dim_vector), way(n, dim_vector);
int tek_position[n];
memset(tek_position, 0, sizeof(int) * n);
while (Check(tek_position, dim_vector, n)) {
int step = (1 < n) - 1;
while (step) {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sum += ((step_vector & (1 << i)) && (step_vector & (1 << j))) ?
score_matrix[index_arr[seq[i][tek_position[i]]]][index_arr[seq[j][tek_position[j]]]] :
penalty * (((step_vector & (1 << i)) == 0) + ((step_vector & (1 << j)) == 0));
}
}
int tek_score = matrix.get(tek_position);
GoTo(tek_position, n, step_vector);
if (way.get(tek_position) == 0) {
matrix.set(tek_position, tek_score + sum);
way.set(tek_position, step_vector);
} else if (matrix.get(tek_position) > tek_score + sum) {
matrix.set(tek_position, tek_score + sum);
way.set(tek_position, step_vector);
}
GoBack(tek_position, n, step_vector);
step_vector--;
}
}
//Конец=======================================================================
for (int i = 0; i < alphabet.length(); i++) {
delete[] score_matrix[i];
}
delete[] score_matrix;
delete[] seq;
return 0;
}