#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 1010
#define INF 0xfffffff int a[*Maxn],sum[*Maxn];
int f[*Maxn][*Maxn],s[*Maxn][*Maxn]; int mymin(int x,int y) {return x<y?x:y;} int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) a[i+n]=a[i];
sum[]=;
for(int i=;i<=*n;i++) sum[i]=sum[i-]+a[i];
memset(f,,sizeof(f));
for(int i=;i<=*n;i++) f[i][i]=,s[i][i]=i;
for(int i=*n;i>=;i--)
for(int j=i+;j<=*n;j++)
{
if(j-i+>n) break;
for(int k=s[i][j-];k<=s[i+][j];k++)
{
if(f[i][j]>f[i][k]+f[k+][j]+sum[j]-sum[i-])
{
f[i][j]=f[i][k]+f[k+][j]+sum[j]-sum[i-];
s[i][j]=k;
}
}
}
int ans=INF;
for(int i=;i<=n;i++) ans=mymin(ans,f[i][i+n-]);
printf("%d\n",ans);
}
return ;
}
其实就是个区间DP的优化,环形石子,把它拆成链就好了【在右面copy一倍】
四边形不等式优化DP
2016-11-18 08:51:01
【无聊放个模板系列】HDU 3506 (四边形不等式优化DP-经典石子合并问题[环形])的更多相关文章
-
【无聊放个模板系列】BZOJ 1597 斜率优化
STL 双向队列DEQUE版本 #include<cstdio> #include<cstdlib> #include<cstring> #include<i ...
-
hdu 2829 Lawrence(四边形不等式优化dp)
T. E. Lawrence was a controversial figure during World War I. He was a British officer who served in ...
-
【转】斜率优化DP和四边形不等式优化DP整理
(自己的理解:首先考虑单调队列,不行时考虑斜率,再不行就考虑不等式什么的东西) 当dp的状态转移方程dp[i]的状态i需要从前面(0~i-1)个状态找出最优子决策做转移时 我们常常需要双重循环 (一重 ...
-
BZOJ1563/洛谷P1912 诗人小G 【四边形不等式优化dp】
题目链接 洛谷P1912[原题,需输出方案] BZOJ1563[无SPJ,只需输出结果] 题解 四边形不等式 什么是四边形不等式? 一个定义域在整数上的函数\(val(i,j)\),满足对\(\for ...
-
codevs3002石子归并3(四边形不等式优化dp)
3002 石子归并 3 参考 http://it.dgzx.net/drkt/oszt/zltk/yxlw/dongtai3.htm 时间限制: 1 s 空间限制: 256000 KB 题目等级 ...
-
CF321E Ciel and Gondolas Wqs二分 四边形不等式优化dp 决策单调性
LINK:CF321E Ciel and Gondolas 很少遇到这么有意思的题目了.虽然很套路.. 容易想到dp \(f_{i,j}\)表示前i段分了j段的最小值 转移需要维护一个\(cost(i ...
-
HDU 2829 Lawrence (斜率优化DP或四边形不等式优化DP)
题意:给定 n 个数,要你将其分成m + 1组,要求每组数必须是连续的而且要求得到的价值最小.一组数的价值定义为该组内任意两个数乘积之和,如果某组中仅有一个数,那么该组数的价值为0. 析:DP状态方程 ...
-
四边形不等式优化DP——石子合并问题 学习笔记
好方啊马上就要区域赛了连DP都不会QAQ 毛子青<动态规划算法的优化技巧>论文里面提到了一类问题:石子合并. n堆石子.现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆石子合并成新的 ...
-
POJ 1160 四边形不等式优化DP Post Office
d(i, j)表示用i个邮局覆盖前j个村庄所需的最小花费 则有状态转移方程:d(i, j) = min{ d(i-1, k) + w(k+1, j) } 其中w(i, j)的值是可以预处理出来的. 下 ...
随机推荐
-
LINUX 文件权限详解
ls -l // 查看文件的权限 等价于 ll 文件的权限信息查看 -rw-rw-r-- 1 ceshi ceshi 891 Aug 8 17:28 server drwxrwxr-x 10 cesh ...
-
Unity全视角跟随鼠标右键转换视角实现——研究笔记
using UnityEngine; using System.Collections; public class CameraMove : MonoBehaviour { public Transf ...
-
有关segue的简介
- (void)prepareForSegue:(UIStoryboardSegue *)segue sender:(id)sender { ViewControllerB *vc = segue ...
-
Unity3D手势及重力加速度(神庙逃亡操作)
Unity实现神庙逃亡操作 现在特别火的跑酷游戏<神庙逃亡>是用Unity3D引擎开发的 游戏的操作:用手指拨动(划动)人物就转向,利用手机的重力感应进行人物左右调整. 今天用Unity来 ...
-
UVA 12906 Maximum Score 排列组合
Maximum Score Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/contest/vie ...
-
SQLLite 简介
[1] SQLite,是一款轻型的数据库,是遵守ACID的关系型数据库管理系统,它的设计目标是嵌入式的,而且目前已经在很多嵌入式产品中使用了它,它占用资源非常的低,在嵌入式设备中,可能只需要几百K的内 ...
-
用python实现文件读取和内容替换
infile = open("D:/test.txt", "r") #打开文件 outfile = open("D:/pp2.txt", & ...
-
IOS学习之路五(代码实现UITableView)
先展示一下运行结果: 代码实现: 1.先创建一个空项目: 2.创建一个Controller:(TableViewController) 在AppDelegate.h中声明属性: // AppDele ...
-
【转】20条Linux命令面试问答
问:1 如何查看当前的Linux服务器的运行级别? 答: ‘who -r’ 和 ‘runlevel’ 命令可以用来查看当前的Linux服务器的运行级别. 问:2 如何查看Linux的默认网关? 答: ...
-
LeetCode 142. Linked List Cycle II 判断环入口的位置 C++/Java
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To r ...