魈凯KBS • 4个月前
#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;//雪花飘飘~~
}
评论: