题目描述
给定一个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N－2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？这应该怎么计算呢？
输入
第一行为顶点数N，第二行为 N个顶点（从1到N）的权值。
输出
第一行为最小的和的值。
第二行为各三角形组成的方式。各三角形各顶点之间以空格间隔，顶点从小到大排序，三角形之间从左到右按字典序排序，中间的逗号为半角字符。
样例输入
5
121 122 123 245 231样例输出
12214884
1 2 3，1 3 5，3 4 5
剖分问题，找最后一个决策点就行了，注意要输出方案。
设dp[i][j]表示从i到j进行三角形划分能得到的最大值，显然有dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+val[i]*val[j]*val[k])枚举分割点k，时间复杂度O(n^3).
注意写高精度！！！
上代码。
1 #include<bits/stdc++.h> 2 #define mod 10000 3 #define maxn 305 4 #define N 105 5 using namespace std; 6 struct HP { 7 int len; 8 long long p[maxn]; 9 HP &operator = (const char *); 10 HP &operator = (long long); 11 HP(){memset(p,0,sizeof(p));len=1;} 12 HP(long long); 13 14 bool operator >(const HP &) const; 15 bool operator <(const HP &) const; 16 bool operator <=(const HP &) const; 17 bool operator >=(const HP &) const; 18 bool operator !=(const HP &) const; 19 bool operator ==(const HP &) const; 20 21 HP operator + (const HP &) const; 22 HP operator - (const HP &) const; 23 HP operator * (const HP &) const; 24 HP operator / (const HP &) const; 25 HP operator % (const HP &) const; 26 27 HP &operator +=(const HP &); 28 HP &operator -=(const HP &); 29 HP &operator *=(const HP &); 30 HP &operator /=(const HP &); 31 HP &operator %=(const HP &); 32 }; 33 HP & HP::operator = (const char *str) { 34 memset(p,0,sizeof(p)); 35 int n=strlen(str),j=1,k=1; 36 for(int i=1;i<=n;i++){ 37 if(k==mod) j++,k=1; 38 p[j]+=k*(str[n-i]-'0'); 39 k*=10; 40 } 41 len=j; 42 return *this; 43 } 44 HP & HP::operator = (long long num) { 45 char s[101]; 46 sprintf(s,"%d",num); 47 return *this=s; 48 } 49 HP::HP(long long num) {*this=num;} 50 bool HP::operator <(const HP &a)const { 51 if(len<a.len) return 1; 52 else if(len>a.len) return 0; 53 else { 54 int i=len; 55 while(i>=1) { 56 if(p[i]<a.p[i]) return 1; 57 else if(p[i]>a.p[i]) return 0; 58 else i--; 59 } 60 return 0; 61 } 62 } 63 bool HP::operator >(const HP &b) const {return b<*this;} 64 bool HP::operator <=(const HP &b) const {return !(*this>b);} 65 bool HP::operator >=(const HP &b) const {return !(*this<b);} 66 bool HP::operator !=(const HP &b) const {return (b<*this)||(*this<b);} 67 bool HP::operator ==(const HP &b) const {return !(*this<b)&&!(b<*this);} 68 69 HP HP::operator + (const HP &b)const { 70 HP c; 71 c.len=len>b.len?len:b.len; 72 int i=1; 73 while(i<=c.len) { 74 c.p[i]+=p[i]+b.p[i]; 75 if(c.p[i]>=mod) { 76 c.p[i+1]++,c.p[i]-=mod; 77 } 78 i++; 79 } 80 if(c.p[c.len+1]>0) c.len++; 81 return c; 82 } 83 HP HP::operator -(const HP &b)const{ //a-b 84 HP c; 85 c.len=len; 86 for(int i=1; i<=c.len; i++) { 87 c.p[i]+=p[i]-b.p[i]; 88 if(c.p[i]<0) { 89 c.p[i]+=mod; 90 c.p[i+1]--; 91 } 92 } 93 while(c.p[c.len]==0&&c.len>1) c.len--; 94 return c; 95 } 96 HP &HP::operator +=(const HP &b) {return *this=*this+b;} 97 HP &HP::operator -=(const HP &b) {return *this=*this-b;} 98 HP HP::operator *(const HP &b)const{ 99 HP c; 100 int i=1,j=1,k=1; 101 c.len=len+b.len+1; 102 while(i<=len) { 103 k=i; 104 j=1; 105 while(j<=b.len) { 106 c.p[k]+=p[i]*b.p[j]; 107 if(c.p[k]>=mod) {c.p[k+1]+=c.p[k]/mod,c.p[k]%=mod;} 108 k++,j++; 109 } 110 i++; 111 } 112 while(c.p[c.len]==0&&c.len>1) c.len--; 113 return c; 114 } 115 HP &HP::operator *=(const HP &b){return *this=*this*b;} 116 HP HP::operator /(const HP &b)const { // a/b 117 HP c,d; 118 c.len=len; 119 d.len=0; 120 for(int i=len; i>=1; i--) { 121 d=d*HP(mod)+p[i]; 122 long long left=0,right=9999,mid; 123 while(left<right) { 124 mid=(left+right)/2; 125 if(b*HP(mid)<=d) left=mid+1; 126 else right=mid; 127 } 128 long long ans1=right-1; 129 long long ans2=right; 130 if(HP(ans2)*b<=d) ans1=ans2; 131 c.p[i]=ans1; 132 d=d-b*HP(ans1); 133 } 134 while(c.p[c.len]==0&&c.len>1) c.len--; 135 return c; 136 } 137 HP HP::operator %(const HP &b)const { 138 HP c,d; 139 c.len=len+b.len+1; 140 d.len=0; 141 for(int i=len; i>=1; i--) { 142 d=d*HP(mod)+p[i]; 143 long long left=0,right=9999,mid; 144 while(left<right) { 145 mid=(left+right)/2; 146 if(b*HP(mid)<=d) left=mid+1; 147 else right=mid; 148 } 149 long long ans1=right-1; 150 long long ans2=right; 151 if(HP(ans2)*b<=d) ans1=ans2; 152 c.p[i]=ans1; 153 d=d-b*HP(ans1); 154 } 155 while(c.p[c.len]==0&&c.len>1) c.len--; 156 return d; 157 } 158 HP &HP::operator /=(const HP &b){*this=*this/b;} 159 HP &HP::operator %=(const HP &b){*this=*this%b;} 160 ostream & operator << (ostream &o,HP &n) { 161 o<<n.p[n.len]; 162 for(int i=n.len-1; i>=1; i--) { 163 o.width(4); 164 o.fill('0'); 165 o<<n.p[i]; 166 } 167 return o; 168 } 169 istream & operator >> (istream & in,HP &n) { 170 char s[maxn]; 171 in>>s; 172 n=s; 173 return in; 174 } 175 //前面是高精度模板 176 177 HP s[N];//保存节点的数组也要有高精度！！之前一直没注意，两个点一直WA 178 HP dp[N][N]; 179 struct ANS{ 180 int x,y,z; 181 bool operator <(const ANS&t)const{ 182 if(x!=t.x) return x<t.x; 183 if(y!=t.y) return y<t.y; 184 if(z!=t.z) return z<t.z; 185 } 186 }res[N];//res数组保存的是我们最终的分解方案 187 int ans[N][N];//ans[i][j]表示将i节点，j节点，ans[i][j]节点划分为一个三角形 188 int ct; 189 inline void dfs(int x,int z){ 190 if(ans[x][z]==0) return ; 191 res[++ct].x=x,res[ct].y=ans[x][z],res[ct].z=z; 192 dfs(x,ans[x][z]),dfs(ans[x][z],z); 193 }//递归求解方案。 194 int n; 195 int main(){ 196 scanf("%d",&n); 197 for(register int i=1;i<=n;i++) cin>>s[i]; 198 for(register int i=n;i>=1;i--){ 199 for(register int j=i+1;j<=n;j++){ 200 for(register int k=i+1;k<j;k++){ 201 if(i==j||i==k||j==k) continue; 202 HP c=dp[i][k]+dp[k][j]+s[i]*s[j]*s[k]; 203 //从i到k进行划分的值加上从k到j划分的值再加上i,j,k划分为一个三角形的值 204 if(dp[i][j].len==1&&dp[i][j].p[1]==0) dp[i][j]=c,ans[i][j]=k;//如果当前状态未被更新，则更新 205 else if(dp[i][j]>c){ 206 dp[i][j]=c; 207 ans[i][j]=k;//记录方案 208 } 209 } 210 } 211 } 212 dfs(1,n); 213 sort(res+1,res+1+ct); 214 cout<<dp[1][n]; 215 if(dp[1][n].len==1&&dp[1][n].p[1]==0) return 0;//没有用的判断。。。 216 printf("\n"); 217 for(register int i=1;i<ct;i++){ 218 printf("%d %d %d,",res[i].x,res[i].y,res[i].z); 219 } 220 printf("%d %d %d",res[ct].x,res[ct].y,res[ct].z);//完结撒花 221 return 0; 222 }