多边形划分

区间dp中仅次于石子合并的经典题， 区间dp的思想我应该不用细说了， 枚举断点，状态转移就完了

题目做法

让我们从一个三角形开始，乘就完了，这样能算出所有相邻三个点组成的三角形。

然后是四边形，划分方法一共两种，定下两个点，要么这两个点和左边的点组成三角形，再加右边的三角形，要么反过来。我们已经算出了其中一个三角形，只要加上两个定点和选出的点组成的三角形即可。

五边形也差不多，一共三种方法，你会发现，每种方法中除了选出的断点和两个定点组成的三角形以外，我们在前面的步骤中都已经算出来了。我们只要用左边加右边再算出中间就行。

n边形的划分经过上面的推导，相信聪明的你已经想到办法了。 让我们枚举一个断点i

dp[l][r]=dp[l][i]+dp[i][r]+中间三角形

好，直接敲，自信提交，WA了

请仔细阅读数据范围 每个点权值小于$\red{10^9}$。

没错，这题还得加高精度。

上代码

//要是想高精度短点可以不维护长度，就是时间会多一点。
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#define LL long long
#define IL inline
const int N = 1e2+10;
const int INF = 0x3f3f3f3f;
using namespace std;
int n,num[N][N],dp[N][N][N],sum[N],pre[N];//数组下表为0的数代表长度
char s[20];
IL int read()
{
    char ch = getchar();
    int f = 1, num = 0;
    while(ch>'9'||ch<'0')
    {
        if(ch=='-') f = -1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        num = num*10+ch-'0', ch = getchar();
    return num*f;
}
void print()
{
    for(int i = dp[1][n][0];i>=1;i--)
        printf("%d",dp[1][n][i]);
    puts("");
}
void get(int id)//输入数组
{
    num[id][0]=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        s[++num[id][0]]=ch,ch=getchar();
    for(int i = 1,j=num[id][0];i<=num[id][0];i++,j--)
        num[id][i]=s[j]-'0';
}
void push(int opt)//更新长度
{
    if(opt)   
        while(sum[sum[0]+1]) sum[0]++;
    else   
        while(pre[pre[0]+1]) pre[0]++;
}
void Mul(int l,int k,int r)//为了主程序简洁点干脆全写一起了
{
    memset(pre,0,sizeof(pre));
    memset(sum,0,sizeof(sum));
    pre[0]=num[l][0]+num[r][0]-1;
    for(int i = 1;i<=num[l][0];i++)
        for(int j = 1;j<=num[r][0];j++)
        {
            pre[i+j-1]+=num[l][i]*num[r][j];
            pre[i+j]+=pre[i+j-1]/10;
            pre[i+j-1]%=10;
        }
    push(0);
    sum[0]=pre[0]+num[k][0]-1;
    for(int i = 1;i<=pre[0];i++)
        for(int j = 1;j<=num[k][0];j++)
        {
            sum[i+j-1]+=pre[i]*num[k][j];
            sum[i+j]+=sum[i+j-1]/10;
            sum[j+i-1]%=10;
        }
    push(1);
}
void Add(int l,int i,int r)//懒得加两次
{
    sum[0]=max(sum[0],max(dp[l][i][0],dp[i][r][0]));
    for(int k = 1;k<=sum[0];k++)
    {
        sum[k]+=dp[l][i][k]+dp[i][r][k];
        sum[k+1]+=sum[k]/10;
        sum[k]%=10;
    }
    push(1);
}
bool Com(int l,int r)//比较
{
    if(!dp[l][r][0]) return true;
    if(sum[0]!=dp[l][r][0]) return sum[0]<dp[l][r][0];
    for(int i = sum[0];i>=1;i--)
        if(sum[i]>dp[l][r][i])
            return false;
        else if(sum[i]<dp[l][r][i])
            return true;
    return false;
}
void calc(int l,int r,int i)
{
    Mul(l,i,r);
    Add(l,i,r);
    if(Com(l,r))
        memcpy(dp[l][r],sum,sizeof(dp[l][r]));
}
int main()
{
    n=read();
    for(int i = 1;i<=n;i++)
        get(i);

    for(int k = 2;k<=n-1;k++)
        for(int l = 1,r=l+k;r<=n;l++,r++)
            for(int i = l+1;i<=r-1;i++)
                calc(l,r,i);
    print();
}

A完之后看别人代码，好家伙我高精度也太长了。

备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N];
int dp[N][N][41];
void calc(int t[], int s)
{
	int k = 0;
	for(int i = 0; i < 40; i++)
	{
		t[i] = t[i] * s + k;
		k = t[i] / 10;
		t[i] %= 10;
	}
}
void add(int t[], int dp[])
{
	for(int i = 0; i < 40; i++)
	{
		t[i] += dp[i];
		t[i+1] += t[i] / 10;
		t[i] %= 10;
	}
}
bool cmp(int t[], int dp[])
{
	for(int i = 40; i >= 0; i--)
	{
		if(t[i] > dp[i])
			return false;
		else if(t[i] < dp[i])
			return true;
	}
	return false;
}
void print(int dp[])
{
	int k = 40;
	while(dp[k] == 0)
		k--;
	for(int i = k; i >= 0; i--)
	{
		cout << dp[i];
	}
	cout << endl;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for(int k = 3; k <= n; k++)
	{
		for(int l = 1; l <= n-k+1; l++)
		{
			int r = l+k-1;
			dp[l][r][40] = 1;
			for(int i = l+1; i < r; i++)
			{
				int t[41];
				memset(t, 0, sizeof(t));
				t[0] = 1;
				calc(t, a[i]);
				calc(t, a[l]);
				calc(t, a[r]);
				add(t, dp[l][i]);
				add(t, dp[i][r]);
				if(cmp(t, dp[l][r]))
					memcpy(dp[l][r], t, sizeof(t));
			}
		}
	}
	print(dp[1][n]);
	return 0;
}

备注：
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N];
int dp[N][N][41];
void calc(int t[], int s)
{
int k = 0;
for(int i = 0; i < 40; i++)
{
t[i] = t[i] * s + k;
k = t[i] / 10;
t[i] %= 10;
}
}
void add(int t[], int dp[])
{
for(int i = 0; i < 40; i++)
{
t[i] += dp[i];
t[i+1] += t[i] / 10;
t[i] %= 10;
}
}
bool cmp(int t[], int dp[])
{
for(int i = 40; i >= 0; i--)
{
if(t[i] > dp[i])
return false;
else if(t[i] < dp[i])
return true;
}
return false;
}
void print(int dp[])
{
int k = 40;
while(dp[k] == 0)
k--;
for(int i = k; i >= 0; i--)
{
cout << dp[i];
}
cout << endl;
}
signed main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
for(int k = 3; k <= n; k++)
{
for(int l = 1; l <= n-k+1; l++)
{
int r = l+k-1;
dp[l][r][40] = 1;
for(int i = l+1; i < r; i++)
{
int t[41];
memset(t, 0, sizeof(t));
t[0] = 1;
calc(t, a[i]);
calc(t, a[l]);
calc(t, a[r]);
add(t, dp[l][i]);
add(t, dp[i][r]);
if(cmp(t, dp[l][r]))
memcpy(dp[l][r], t, sizeof(t));
}
}
}
print(dp[1][n]);
return 0;
}