题意
给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形,试求这些三角形顶点的权值乘积和至少为多少。思路
首先随便搞一个多边形:$$f[i][j]=min{f[i][k]+f[k][j]+a[i]a[j]a[k]}(0<i<j<k\leq n)$$
初始化:
$$f[i][j]=inf(0<i\leq n,0<j\leq n)$$ $$f[i][i+1]=0(0<i<n)$$ 时间复杂度:$O(n^3)$ 输出结果:$f[1][n]$ 当然,这道题范围特别大:对于 $100\%$ 的数据,有 $N\le 50$,每个点权值小于 $10^9$。三个数相乘最高可达$10^{27}$,所以需要使用高精度。这里使用了C++大数类,转自代号4101
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 |
#include<bits/stdc++.h> using namespace std; const int maxn = 1000; struct bign{ int d[maxn], len; void clean() { while(len > 1 && !d[len-1]) len--; } bign() { memset(d, 0, sizeof(d)); len = 1; } bign(int num) { *this = num; } bign(char* num) { *this = num; } bign operator = (const char* num){ memset(d, 0, sizeof(d)); len = strlen(num); for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0'; clean(); return *this; } bign operator = (int num){ char s[20]; sprintf(s, "%d", num); *this = s; return *this; } bign operator + (const bign& b){ bign c = *this; int i; for (i = 0; i < b.len; i++){ c.d[i] += b.d[i]; if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++; } while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++; c.len = max(len, b.len); if (c.d[i] && c.len <= i) c.len = i+1; return c; } bign operator - (const bign& b){ bign c = *this; int i; for (i = 0; i < b.len; i++){ c.d[i] -= b.d[i]; if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--; } while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--; c.clean(); return c; } bign operator * (const bign& b)const{ int i, j; bign c; c.len = len + b.len; for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) c.d[i+j] += d[i] * b.d[j]; for(i = 0; i < c.len-1; i++) c.d[i+1] += c.d[i]/10, c.d[i] %= 10; c.clean(); return c; } bign operator / (const bign& b){ int i, j; bign c = *this, a = 0; for (i = len - 1; i >= 0; i--) { a = a*10 + d[i]; for (j = 0; j < 10; j++) if (a < b*(j+1)) break; c.d[i] = j; a = a - b*j; } c.clean(); return c; } bign operator % (const bign& b){ int i, j; bign a = 0; for (i = len - 1; i >= 0; i--) { a = a*10 + d[i]; for (j = 0; j < 10; j++) if (a < b*(j+1)) break; a = a - b*j; } return a; } bign operator += (const bign& b){ *this = *this + b; return *this; } bool operator <(const bign& b) const{ if(len != b.len) return len < b.len; for(int i = len-1; i >= 0; i--) if(d[i] != b.d[i]) return d[i] < b.d[i]; return false; } bool operator >(const bign& b) const{return b < *this;} bool operator<=(const bign& b) const{return !(b < *this);} bool operator>=(const bign& b) const{return !(*this < b);} bool operator!=(const bign& b) const{return b < *this || *this < b;} bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);} string str() const{ char s[maxn]={}; for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0'; return s; } }; istream& operator >> (istream& in, bign& x){ string s; in >> s; x = s.c_str(); return in; } ostream& operator << (ostream& out, const bign& x){ out << x.str(); return out; } #define ll bign ll f[55][55],a[55]; int n; int main(){ cin>>n; for(int i=1;i<=n;i+=1) cin>>a[i]; memset(f,63,sizeof(f)); for(int i=1;i<=n;i++) f[i][i+1]=0; for(int L=2;L<=n-1;L++){ for(int i=1;i<=n-L;i++){ int j=i+L; for(int k=i+1;k<=j-1;k++){ f[i][j]=min(f[i][k]+f[k][j]+a[i]*a[j]*a[k],f[i][j]); } } } cout<<f[1][n];putchar('\n'); return 0; } //f[i][j]=min{f[i][k]+f[k][j]+a[i]*a[j]*a[k]}(0<i<k<j<=n) //f[i][j]=inf //f[i][i+1]=0; //end:f[1][n] //Time:O(n^3) |