hdu4960 区间dp

news/2024/10/31 3:19:12/

由于可以预处理出每个左端点对应的右端点,所以并不需要开二维,复杂度应该是介于n和n^2之间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;int n;
ll a[5010];
int cost[5010];
int dp[5010];
ll ls[5010],rs[5010];int Find(int x)
{int l=0,r=n+1;while(l<=r){int m=(l+r)>>1;if(rs[m]==ls[x]) return m;if(rs[m]<ls[x]) r=m-1;else l=m+1;}return -1;
}
int F[5010];int dfs(int l,int r)
{int &res=dp[l];if(~res) return res;if(l>r) return res=0;res=cost[r-l+1];int k2;REP(k,l,r-1){k2=F[k];if(k2==-1||k>=k2) continue;res=min(res,cost[k-l+1]+cost[r-k2+1]+dfs(k+1,k2-1));}return res;
}int main()
{//freopen("in.txt","r",stdin);while(~scanf("%d",&n)&&n){REP(i,1,n) scanf("%I64d",&a[i]);a[0]=a[n+1]=0;REP(i,1,n) scanf("%d",&cost[i]);ls[0]=0;REP(i,1,n) ls[i]=ls[i-1]+a[i];rs[n+1]=0;for(int i=n;i>=1;i--) rs[i]=rs[i+1]+a[i];REP(i,1,n) F[i]=Find(i);memset(dp,-1,sizeof(dp));printf("%d\n",dfs(1,n));}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/--560/p/5354545.html


http://www.ppmy.cn/news/460660.html

相关文章

hdu 4960 数列合并

http://acm.hdu.edu.cn/showproblem.php?pid4960 给定一个长度为n的序列&#xff0c;然后再给出n个数bi,表示合成i个数的代价。每次可以将连续的子序列和成一个数&#xff0c;即为序列中各个项的和。要求将给定长度n的序列变成一个回文串&#xff0c;一个数字只能被合成一次。…

uvalive 4960 Sensor Network

题意&#xff1a; 给出一个无向图&#xff0c;求一个生成树使得这个生成树的最大边与最小边之差最小&#xff0c;输出这个最小的差值。n的最大值为350。 思路&#xff1a; 这题不看题解想破头也不知道怎么写Orz。 暴力的做法是可以从大到小枚举边作为最小边的权值&#xff0c;求…

4960x支持服务器内存吗,提升不到10%:i7-4960x六核处理器实测

泡泡网CPU频道4月26日 Intel的新一代发烧处理器Ivy Bridge-E将在11月份发布,而到那个时候,Sandy Bridge-E平台将会坚守长达两年时间,这在顶级产品上是很不可思议的。正因为如此,很多发烧友对Ivy Bridge-E都期待万分,特别是它还继续兼容LGA2011接口和X79芯片组。 那么Ivy B…

0008-TIPS-2020-hxp-kernel-rop : bypass-FGKASLR-with-unaffected_gadgets

利用 CTF-WKI中描述中的缺点&#xff1a;.text 节区不参与函数随机化。因此&#xff0c;一旦知道其中的某个地址&#xff0c;就可以获取该节区所有的地址。有意思的是系统调用的入口代码都在该节区内&#xff0c;主要是因为这些代码都是汇编代码。此外&#xff0c;该节区具有以…

国产麒麟服务器等保二级 配置规范(二)

一、redis的配置规范 1.1 禁止以root账号运行redis服务 以下Linux 命令操作创建了一个无 home 目录权限&#xff0c;且无法登录的普通账号redis。 #useradd -M -s /sbin/nologin redis 修改服务允许和配置文件权限&#xff1a; #setsid sudo -u redis /usr/bin/redis-serer /e…

Kafka源码解析之索引

Kafka源码解析之索引 索引结构 Kafka有两种类型的索引&#xff1a; TimeIndex: 根据时间戳索引&#xff0c;可以通过时间查找偏移量所在位置&#xff0c;目录下以.timeindex结尾Index: 根据偏移量索引&#xff0c;.index结尾 构建索引时机 由log.index.interval.bytes 参…

Android——如何在电脑里找到手机中的图片或者视频

1.先让你的手机与你的电脑进行多媒体的连接 2.首先找到你的Android的SDK目录&#xff0c;然后进入platform-tools目录下&#xff0c;然后shift鼠标右键&#xff0c;选择在此处打开cmd或Powershell窗口&#xff0c;然后执行adb shell命令即可 3.然后我们在手机中随便找一个图片…