Codeforces1140D. Minimum Triangulation
2024-09-06 23:44:01
本题是区间dp里的三角剖分,板子题,dp[i][j]表示凸多边形i-j构成的最值,转移方程为dp[i][j] = min/max(dp[i][k]+dp[k][j]+w[i,j,k])(i<k<j),表示将凸多边形i-j以k为分界,分成i-k,k-j以及三角形i-j-k
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
typedef pair<int,int> pii; const LL INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = ;
LL dp[maxn][maxn]; void run_case() {
int n; cin >> n;
for(int i = n-; i >= ; --i) {
for(int j = i+; j <= n; ++j) {
dp[i][j] = INF;
for(int k = i+; k < j; ++k)
dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]+i*j*k);
}
}
cout << dp[][n];
} int main() {
ios::sync_with_stdio(false), cin.tie();
cout.flags(ios::fixed);cout.precision();
//int t; cin >> t;
//while(t--)
run_case();
cout.flush();
return ;
}
最新文章
- 4.5 .net core下直接执行SQL语句并生成DataTable
- JavaScript闭包浅谈
- Python爬虫入门一之综述
- 黑马程序员:Java编程_网络编程
- 《锋利的jQuery》(第2版)读书笔记4
- TP学习笔记一(tp的目录结构 , tp的输出方式)
- 线段树单点更新poj 2828
- MBR(Master Boot Record)主引导记录分析
- Codeforces Round #335 (Div. 1) C. Freelancer&#39;s Dreams 计算几何
- C#编程使用到的几种调试方式
- xss 跨站脚本攻击
- Mybatis在oracle、mysql、db2、sql server的like模糊查询
- 【Struts2学习笔记(11)】对action的输入校验和XML配置方式实现对action的全部方法进行输入校验
- Apache Kafka系列(三) Java API使用
- js解决IE8不支持html5,css3的问题(respond.js 的使用注意)
- AspNetCore Mvc 使用 PartialView
- Spring拓展接口之FactoryBean,我们来看看其源码实现
- python3+requests库框架设计03-请求重新封装
- mybatis的基础Dao
- java多线程关键字volatile、lock、synchronized