刷题记录:牛客NC50500凸多边形的划分

传送门:牛客

主要思路:

给定一个具有N个顶点的凸多边形，将顶点从1至N标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成N-2个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。
输入:
5
121 122 123 245 231
输出:
12214884

一道巧妙的区间dp的题目(emmm,虽然我们感觉只要是dp都是挺巧妙的…)

主要思路:

1. 我们经过手模一下应该不难发现假定我们显然如果有四个点的话,显然我们可以经过第二点或者第三点和我们的首点和终点连接分成四个三角形的形式.当然点更多时也是一样,那么这就相当于一个区间dp的模板了.接下来只要使用区间dp即可

$dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]\ast a[k]\ast a[r])$

2. 注意此题的范围已经超过了$longlong$,但是幸运的是我们有__int128,所以我们可以使用此结构水一下高精度,这不快乐的一批

关于__int128的输出函数:

void print(ll num){
	if(num>9) print(num/10);
	putchar(num%10+'0');
}

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef __int128 ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;ll dp[60][60];
ll a[100];
void print(ll num){
	if(num>9) print(num/10);
	putchar(num%10+'0');
}
int main() {
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int len=3;len<=n;len++) {
		for(int l=1;l+len-1<=n;l++) {
			int r=l+len-1;
			dp[l][r]=1e30;
			for(int k=l+1;k<=r-1;k++) {
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+a[l]*a[k]*a[r]);
			}
		}
	}
	print(dp[1][n]);
	return 0;
}