SOJ-2708(簡単dp、パスはあまり記録されません)
4638 ワード
他の人が結果の経路を記録する方法を参考にして、残りは自分の考えです.
double a[30];
double d[30][30];
double ans[10005][30];
int path[10005][30];
char s[10000];
void process(char c)
{
int i;
switch (c) {
case '2':
for (i = 0; i < 3; ++i)
ans[0][i] = a[i];
break;
case '3':
for (i = 3; i < 6; ++i)
ans[0][i] = a[i];
break;
case '4':
for (i = 6; i < 9; ++i)
ans[0][i] = a[i];
break;
case '5':
for (i = 9; i < 12; ++i)
ans[0][i] = a[i];
break;
case '6':
for (i = 12; i < 15; ++i)
ans[0][i] = a[i];
break;
case '7':
for (i = 15; i < 19; ++i)
ans[0][i] = a[i];
break;
case '8':
for (i = 19; i < 22; ++i)
ans[0][i] = a[i];
break;
case '9':
for (i = 22; i < 26; ++i)
ans[0][i] = a[i];
break;
}
}
bool check(int a, char b)
{
if (a >= 0 && a <= 2 && b == '2') return true;
if (a >= 3 && a <= 5 && b == '3') return true;
if (a >= 6 && a <= 8 && b == '4') return true;
if (a >= 9 && a <= 11 && b == '5') return true;
if (a >= 12 && a <= 14 && b == '6') return true;
if (a >= 15 && a <= 18 && b == '7') return true;
if (a >= 19 && a <= 21 && b == '8') return true;
if (a >= 22 && a <= 25 && b == '9') return true;
return false;
}
void easy(int a, int b, int in)
{
int i, j;
for (i = a; i < b; ++i) {
double max = -1;
int index = 0;
for (j = 0; j < 26; ++j) {
if ((d[j][i]) > 0 && (ans[in - 1][j]) > 0 && check(j, s[in - 1])) {
if (ans[in - 1][j] * d[j][i] > max) {
max = ans[in - 1][j] * d[j][i];
path[in][i] = j;
}
}
}
if (max == -1) max = 0;
ans[in][i] = max;
}
}
void process1(char c, int index)
{
int i, j;
switch (c) {
case '2':
easy(0, 3, index);
break;
case '3':
easy(3, 6, index);
break;
case '4':
easy(6, 9, index);
break;
case '5':
easy(9, 12, index);
break;
case '6':
easy(12, 15, index);
break;
case '7':
easy(15, 19, index);
break;
case '8':
easy(19, 22, index);
break;
case '9':
easy(22, 26, index);
break;
}
}
int main()
{
int i, j;
for (i = 0; i < 26; ++i)
scanf("%lf", &a[i]);
for (i = 0; i < 26; ++i) {
for (j = 0; j < 26; ++j) {
scanf("%lf", &d[i][j]);
}
}
int n;
scanf("%d", &n);
getchar();
while (n--) {
gets(s);
int l = strlen(s);
if (l == 0) {
++n;
continue;
}
memset(ans, 0, sizeof(ans));
memset(path, 0, sizeof(path));
process(s[0]);
for (i = 1; i < l; ++i) {
process1(s[i], i);
}
double max = -1;
int index = 0;
/*
for (i = 0; i < 26; ++i)
printf("%4c ", i + 'a');
printf("
");
for (i = 0; i < l; ++i) {
for (j = 0; j < 26; ++j) {
printf("%lf ", ans[i][j]);
}
printf("
");
}
*/
j = l - 1;
char tt[1000];
int xxx = 0;
for (i = 0; i < 26; ++i) {
if (ans[j][i] > max && check(i, s[j])) {
max = ans[j][i];
index = i;
}
}
tt[xxx++] = index + 'a';
int ta = index;
i = l - 1;
while (i) {
tt[xxx++] = path[i][index] + 'a';
index = path[i][index];
--i;
}
for (i = xxx - 1; i >= 0; --i)
printf("%c", tt[i]);
printf("
");
}
return 0;
}