个人博客网站制作搭建,网站建设专员一定要会网站建设吗,网易企业邮箱邮箱登录入口,安装如WordPressAcwing1069. 凸多边形的划分
题意#xff1a;
一个N个顶点的凸多边形#xff0c;划分成N-2个互不相交的三角形#xff0c;对于每个三角形#xff0c;其三个顶点的权值相乘都可得到一个权值乘积#xff0c;试求所有三角形的顶点权值乘积之和至少为多少。
题解#xff1…Acwing1069. 凸多边形的划分
题意
一个N个顶点的凸多边形划分成N-2个互不相交的三角形对于每个三角形其三个顶点的权值相乘都可得到一个权值乘积试求所有三角形的顶点权值乘积之和至少为多少。
题解
区间dp问题 我们这么想对于顶点i到j的最小权值和是多少 我们在i和j中枚举ki和j形成一个线段加上k就可以组成一个三角形此时剩余部分为i到k和k到j三角形ijk的值我们可以算出剩余部分相当于小区间我们已经提前算出所以取最小就是i到j的答案
我们用f[i][j]表示顶点i到顶点j的最小权值乘积和 f[l][r]min(f[l][r],f[l][k]f[k][r]a[l]*a[k]*a[r]); 本题写高精度或者用__int128
代码
#include bits/stdc.h
using namespace std;
typedef __int128 ll;ll read()
{ll res0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9){res(res3)(res1)(ch^48);chgetchar();}return res*w;
}
void write(ll x)
{if(x0){putchar(-);x-x;}if(x9)write(x/10);putchar(x%100);
}
void writeln(ll x)
{write(x);putchar(\n);
}ll f[110][110],a[110];
int main()
{int nread();for(int i1;in;i)a[i]read(),a[in]a[i];memset(f,127,sizeof(f));for(int i1;in*2;i)f[i][i1]0;for(int len3;lenn;len)for(int l1;ln*2-len1;l){int rllen-1;for(int kl1;kr;k)f[l][r]min(f[l][r],f[l][k]f[k][r]a[l]*a[k]*a[r]);}ll ansf[1][n];for(int i1;in;i)ansmin(ans,f[i][in-1]);write(ans);return 0;
}
