给过不去的仁兄一篇救命题解———看不懂的不要抄

#include<bits/stdc++.h>
#define mod 10000
#define maxn 305
#define N 105
using namespace std;

struct HP {
    int len;
    long long p[maxn];
    HP &operator = (const char *);
    HP &operator = (long long);
    HP() {
        memset(p,0,sizeof(p));
        len=1;
    }
    HP(long long);

    bool operator >(const HP &) const;
    bool operator <(const HP &) const;
    bool operator <=(const HP &) const;
    bool operator >=(const HP &) const;
    bool operator !=(const HP &) const;
    bool operator ==(const HP &) const;

    HP operator + (const HP &) const;
    HP operator - (const HP &) const;
    HP operator * (const HP &) const;
    HP operator / (const HP &) const;
    HP operator % (const HP &) const;

    HP &operator +=(const HP &);
    HP &operator -=(const HP &);
    HP &operator *=(const HP &);
    HP &operator /=(const HP &);
    HP &operator %=(const HP &);
};

HP & HP::operator = (const char *str) {
    memset(p,0,sizeof(p));
    int n = strlen(str), j = 1, k = 1;
    for(int i=1; i<=n; i++) {
        if(k == mod)
            j++, k=1;
        p[j] += k*(str[n-i]-'0');
        k *= 10;
    }
    len = j;
    return *this;
}

HP & HP::operator = (long long num) {
    char s[101];
    sprintf(s, "%d", num);
    return *this = s;
}

HP::HP(long long num) {
    *this = num;
}

bool HP::operator <(const HP &a)const {
    if(len < a.len)
        return 1;
    else if(len > a.len)
        return 0;
    else {
        int i = len;
        while(i >= 1) {
            if(p[i] < a.p[i])
                return 1;
            else if(p[i] > a.p[i])
                return 0;
            else
                i--;
        }
        return 0;
    }
}

bool HP::operator > (const HP &b) const {
    return b < *this;
}

bool HP::operator <= (const HP &b) const {
    return !(*this>b);
}

bool HP::operator >= (const HP &b) const {
    return !(*this<b);
}

bool HP::operator != (const HP &b) const {
    return (b<*this)||(*this<b);
}

bool HP::operator == (const HP &b) const {
    return !(*this<b)&&!(b<*this);
}

HP HP::operator + (const HP &b)const {  //高精加法
    HP c;
    c.len = len>b.len ? len:b.len;
    int i = 1;
    while(i <= c.len) {
        c.p[i] += p[i]+b.p[i];
        if(c.p[i] >= mod)
            c.p[i+1]++, c.p[i]-=mod;
        i++;
    }
    if(c.p[c.len+1] > 0)
        c.len++;
    return c;
}

HP HP::operator - (const HP &b)const { //高精减法
    HP c;
    c.len = len;
    for(int i=1; i<=c.len; i++) {
        c.p[i] += p[i]-b.p[i];
        if(c.p[i] < 0) {
            c.p[i] += mod;
            c.p[i+1]--;
        }
    }
    while(c.p[c.len]==0 && c.len>1)
        c.len--;
    return c;
}

HP &HP::operator += (const HP &b) {
    return *this=*this+b;
}

HP &HP::operator -= (const HP &b) {
    return *this = *this-b;
}
HP HP::operator * (const HP &b) const { //高精乘法
    HP c;
    int i=1, j=1, k=1;
    c.len = len+b.len+1;
    while(i <= len) {
        k = i;
        j = 1;
        while(j <= b.len) {
            c.p[k] += p[i]*b.p[j];
            if(c.p[k] >= mod)
                c.p[k+1] += c.p[k]/mod, c.p[k] %= mod;
            k++, j++;
        }
        i++;
    }
    while(c.p[c.len]==0 && c.len>1)
        c.len--;
    return c;
}

HP &HP::operator *= (const HP &b) {
    return *this = *this*b;
}

HP HP::operator / (const HP &b) const { //高精除法
    HP c, d;
    c.len = len;
    d.len = 0;
    for(int i=len; i>=1; i--) {
        d = d*HP(mod)+p[i];
        long long left = 0, right = 9999, mid;
        while(left < right) {
            mid = (left+right)/2;
            if(b*HP(mid) <= d)
                left=mid+1;
            else
                right = mid;
        }
        long long ans1 = right-1, ans2 = right;
        if(HP(ans2)*b <= d)
            ans1 = ans2;
        c.p[i] = ans1;
        d = d-b*HP(ans1);
    }
    while(c.p[c.len]==0 && c.len>1)
        c.len--;
    return c;
}

HP HP::operator % (const HP &b) const { //高精取余
    HP c, d;
    c.len = len+b.len+1;
    d.len = 0;
    for(int i=len; i>=1; i--) {
        d = d*HP(mod)+p[i];
        long long left = 0, right = 9999, mid;
        while(left < right) {
            mid = (left+right)/2;
            if(b*HP(mid) <= d)
                left = mid+1;
            else
                right = mid;
        }
        long long ans1 = right-1, ans2 = right;
        if(HP(ans2)*b <= d)
            ans1 = ans2;
        c.p[i] = ans1;
        d = d-b*HP(ans1);
    }
    while(c.p[c.len]==0 && c.len>1)
        c.len--;
    return d;
}

HP &HP::operator /= (const HP &b) {
    *this = *this/b;
}

HP &HP::operator %= (const HP &b) {
    *this = *this%b;
}

ostream & operator << (ostream &o, HP &n) {
    o << n.p[n.len];
    for(int i=n.len-1; i>=1; i--) {
        o.width(4);
        o.fill('0');
        o << n.p[i];
    }
    return o;
}

istream & operator >> (istream & in, HP &n) {
    char s[maxn];
    in >> s;
    n = s;
    return in;
}

HP s[N], dp[N][N];
struct ANS {
    int x,y,z;
    bool operator <(const ANS&t)const {
        if(x!=t.x) return x<t.x;
        if(y!=t.y) return y<t.y;
        if(z!=t.z) return z<t.z;
    }
} res[N];
int ct, ans[N][N];
inline void dfs(int x,int z) {
    if(ans[x][z] == 0)
        return;
    res[++ct].x = x,res[ct].y = ans[x][z];
    res[ct].z = z;
    dfs(x, ans[x][z]);
    dfs(ans[x][z], z);
}
int n;
int main() {
    scanf("%d", &n);
    for(register int i=1; i<=n; i++)
        cin >> s[i];
    for(register int i=n; i>=1; i--) {
        for(register int j=i+1; j<=n; j++) {
            for(register int k=i+1; k<j; k++) {
                if(i==j || i==k || j==k)
                    continue;
                HP c = dp[i][k]+dp[k][j]+s[i]*s[j]*s[k];
                if(dp[i][j].len==1 && dp[i][j].p[1]==0)
                    dp[i][j] = c, ans[i][j] = k;
                else if(dp[i][j] > c) {
                    dp[i][j] = c;
                    ans[i][j] = k;
                }
            }
        }
    }
    dfs(1, n);
    sort(res+1, res+1+ct);
    cout << dp[1][n];
    if(dp[1][n].len==1 && dp[1][n].p[1]==0)
        return 0;
    puts("");
    for(register int i=1; i<ct; i++)
        printf("%d %d %d,", res[i].x, res[i].y, res[i].z);
    printf("%d %d %d", res[ct].x, res[ct].y, res[ct].z);
    return 0;
}