12276 - Assembly line

[mehrab2603]

Getting WA. May I get some test cases.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

const int MAX = 30;

struct Return {
    int time, serial;
    Return() {}
    Return(int time, int serial) {
        this->time = time;
        this->serial = serial;
    }
};

int symbols[MAX], revSymbols[MAX];

int timeNeeded[MAX][MAX], transformsTo[MAX][MAX];
Return dp[210][210];
char line[210];
bool vis[210][210];

Return mcm(int, int);

int main() {
    bool start = false;
    int k;
    while(scanf("%d", &k) && k) {
        getchar();
        if(!start) start = true;
        else printf("\n");
        int number = 0;
        while(number < k) {
            char ch = getchar();
            if(ch >= 'a' && ch <= 'z') symbols[ch - 'a'] = number, revSymbols[number++] = ch - 'a';
        }
        getchar();
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < k; j++) {
                int ti;
                char tr;
                scanf("%d-%c", &ti, &tr);
                timeNeeded[i][j] = ti;
                transformsTo[i][j] = symbols[tr - 'a'];
            }
        }
        int n;
        scanf("%d", &n);
        getchar();
        for(int i = 0; i < n; i++) {
            scanf("%s", line);
            getchar();
            memset(vis, false, sizeof vis);
            Return r = mcm(0, strlen(line) - 1);
            printf("%d-%c\n", r.time, revSymbols[r.serial] + 'a');
        }
    }
    return 0;
}

Return mcm(int beg, int fin) {
    if(beg == fin) return Return(0, symbols[line[beg] -'a']);
    if(vis[beg][fin]) return dp[beg][fin];
    int ans = INT_MAX, serial = INT_MAX;
    for(int mid = beg; mid < fin; mid++) {
        Return left = mcm(beg, mid);
        Return right = mcm(mid + 1, fin);
        if(left.time + right.time + timeNeeded[left.serial][right.serial] < ans) {
            ans = left.time + right.time + timeNeeded[left.serial][right.serial];
            serial = transformsTo[left.serial][right.serial];
        }
        else if(left.time + right.time + timeNeeded[left.serial][right.serial] == ans) {
            if(transformsTo[left.serial][right.serial] < serial)
                serial = transformsTo[left.serial][right.serial];
        }
    }
    dp[beg][fin] = Return(ans, serial);
    vis[beg][fin] = true;
    return dp[beg][fin];
}