AcWing 1069 凸多边形的划分 区间dp + 高精度

ops/2024/11/1 1:08:52/

代码

#include <bits/stdc++.h>using namespace std;const int N = 55, M = 35;typedef long long LL;int n;
LL temp[M], w[N];
LL f[N][N][M];void mul(LL a[], LL b)
{LL t = 0;for (int i = 0; i < M; i ++ ){t += a[i] * b;a[i] = t % 10;t /= 10;}
}void add(LL a[], LL b[])
{LL t = 0;for (int i = 0; i < M; i ++ ){t += a[i] + b[i];a[i] = t % 10;t /= 10;}
}int cmp(LL a[], LL b[])
{for (int i = M - 1; i >= 0; i -- ){if (a[i] < b[i] ) return -1;else if (a[i] > b[i]) return 1;}return 0;
}void print (LL a[])
{int k = M - 1;while (k && !a[k]) k --;while (k >= 0) cout << a[k -- ];cout << endl;
}int main()
{cin >> n;for (int i = 1; i <= n; i ++ ) cin >> w[i];for (int len = 3; len <= n; len ++){for (int l = 1; l + len - 1 <= n; l ++ ){int r = l + len - 1;f[l][r][M - 1] = 1;for (int k = l + 1; k < r; k ++ ){memset(temp, 0, sizeof temp);temp[0] = w[l];mul(temp, w[r]);mul(temp, w[k]);add(temp, f[l][k]);add(temp, f[k][r]);if (cmp(temp, f[l][r]) < 0)memcpy(f[l][r], temp, sizeof temp);}}}print(f[1][n]);return 0;
}


http://www.ppmy.cn/ops/129989.html

相关文章

设计一个灵活的RPC架构

RPC架构 RPC本质上就是一个远程调用&#xff0c;需要通过网络来传输数据。传输协议可以有多种选择&#xff0c;但考虑到可靠性&#xff0c;一般默认采用TCP协议。为了屏蔽网络传输的复杂性&#xff0c;需要封装一个单独的数据传输模块用来收发二进制数据&#xff0c;这个单独模…

【Linux网络】传输层协议UDP与TCP

W...Y的主页 &#x1f60a; 代码仓库分享 &#x1f495; 目录 传输层 再谈端口号 ​编辑 端口号范围划分 认识知名端口号(Well-Know Port Number) netstat pidof UDP协议 UDP协议端格式 UDP的特点 面向数据报 UDP的缓冲区 UDP使用注意事项 基于UDP的应用层协议…

01,http 协议

1 &#xff0c;http 协议 &#xff1a;介绍 1 &#xff0c;http &#xff1a;是什么 Hyper Text Transfer Protocol &#xff1a;超文本传输协议 2 &#xff0c;传输内容 &#xff1a;文本 1 &#xff0c;内容 &#xff1a;      纯文本    2 &#xff0c;特殊 &#xf…

我要成为算法高手-滑动窗口篇

目录 滑动窗口算法题目1:长度最小的子数组题目2:无重复字符的最长子串题目3:最大连续1的个数题目4:将x减到0的最小操作数题目5:水果成篮题目6:找到字符串中所有的字母异位词题目7:串联所有单词的子串题目8:最小覆盖子串 滑动窗口算法 滑动窗口的本质还是双指针&#xff0c;只不…

基于Openwrt系统架构,实现应用与驱动的实例。

一、在openwrt系统架构&#xff0c;编写helloworld的应用程序。 第一步先创建目录&#xff0c;项目代码要放在 openwrt根目下的 package 目录中&#xff0c;这里源码写在了 hellworld 的 src 目录下&#xff0c;因为外层还有需要编写的文件。 mkdir -p ~/openwrt/package/hel…

人工智能技术:塑造未来生活与工作的变革力量

人工智能技术&#xff1a;塑造未来生活与工作的变革力量 一、引言 在当今科技飞速发展的时代&#xff0c;人工智能技术如同一颗璀璨的新星&#xff0c;在各个领域绽放出耀眼的光芒&#xff0c;引领着一场前所未有的变革。从医疗领域的精准诊断到企业运营的智能优化&#xff0…

Gateway 统一网关

一、初识 Gateway 1. 为什么需要网关 我们所有的服务可以让任何请求访问&#xff0c;但有些业务不是对外公开的&#xff0c;这就需要用网关来统一替我们筛选请求&#xff0c;它就像是房间的一道门&#xff0c;想进入房间就必须经过门。而请求想要访问微服务&#xff0c;就必须…

外包干了2个月,技术明显退步

回望过去&#xff0c;我是一名普通的本科生&#xff0c;于2019年通过校招有幸加入了南京某知名软件公司。那时的我&#xff0c;满怀着对未来的憧憬和热情&#xff0c;投入到了功能测试的岗位中。日复一日&#xff0c;年复一年&#xff0c;转眼间&#xff0c;我已经在这个岗位上…