题目链接

本题是区间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 ;
}

最新文章

  1. 4.5 .net core下直接执行SQL语句并生成DataTable
  2. JavaScript闭包浅谈
  3. Python爬虫入门一之综述
  4. 黑马程序员:Java编程_网络编程
  5. 《锋利的jQuery》(第2版)读书笔记4
  6. TP学习笔记一(tp的目录结构 , tp的输出方式)
  7. 线段树单点更新poj 2828
  8. MBR(Master Boot Record)主引导记录分析
  9. Codeforces Round #335 (Div. 1) C. Freelancer&#39;s Dreams 计算几何
  10. C#编程使用到的几种调试方式
  11. xss 跨站脚本攻击
  12. Mybatis在oracle、mysql、db2、sql server的like模糊查询
  13. 【Struts2学习笔记(11)】对action的输入校验和XML配置方式实现对action的全部方法进行输入校验
  14. Apache Kafka系列(三) Java API使用
  15. js解决IE8不支持html5,css3的问题(respond.js 的使用注意)
  16. AspNetCore Mvc 使用 PartialView
  17. Spring拓展接口之FactoryBean,我们来看看其源码实现
  18. python3+requests库框架设计03-请求重新封装
  19. mybatis的基础Dao
  20. java多线程关键字volatile、lock、synchronized

热门文章

  1. PyQt5遇到的一个坑 &quot;ImportError: unable to find Qt5Core.dll on PATH&quot; 及解决办法
  2. js判断非127开头的IP地址
  3. python正则--re模块常用方法
  4. 深度学习之tensorflow框架(中)
  5. 欧拉降幂 (a^t)%c 模板
  6. js 实现文字转音频播放
  7. 网络技能大赛A卷测试
  8. alsa driver--card
  9. 【HTTP与HTTPS的区别】
  10. 基于Aspectj表达式配置的Spring AOP