hdu 2829 斜率DP
2024-09-27 18:26:37
思路:dp[i][x]=dp[j][x-1]+val[i]-val[j]-sum[j]*sum[i]+sum[j]*sum[j];
其中val[i]表示1~~i是一段的权值。
然后就是普通斜率dp做法。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstring>
#define Maxn 1010
#define LL __int64
using namespace std;
LL dp[Maxn][Maxn],num[Maxn],sum[Maxn],val[Maxn];
int que[Maxn*];
LL getleft(int x,int j,int k)
{
return dp[j][x]-val[j]+sum[j]*sum[j]-(dp[k][x]-val[k]+sum[k]*sum[k]);
}
LL getright(int j,int k)
{
return sum[j]-sum[k];
}
int main()
{
int n,m,i,j,head,rear;
while(scanf("%d%d",&n,&m)!=EOF,n||m){
memset(dp,,sizeof(dp));
for(i=;i<=n;i++){
scanf("%I64d",num+i);
sum[i]=sum[i-]+num[i];
}
for(i=;i<=n;i++){
val[i]=val[i-]+num[i]*sum[i-];
dp[i][]=val[i];
}
for(j=;j<m;j++){
head=,rear=;
que[++rear]=j;
for(i=j+;i<=n;i++){
while(head<rear&&getleft(j,que[head+],que[head])<sum[i]*getright(que[head+],que[head]))
head++;
dp[i][j+]=dp[que[head]][j]+val[i]-val[que[head]]-sum[que[head]]*sum[i]+sum[que[head]]*sum[que[head]];
while(head<rear&&getleft(j,i,que[rear])*getright(que[rear],que[rear-])<=getleft(j,que[rear],que[rear-])*getright(i,que[rear]))
rear--;
que[++rear]=i;
}
}
printf("%I64d\n",dp[n][m]);
}
return ;
}
最新文章
- HDU 2087 字符串
- iOS 事件传递(Touch事件)
- ZHA profile与ZLL profile的一个例子
- directly receive json data from javascript in mvc
- log4j打印参数
- IIS7 “拒绝访问临时目录”
- 构建移动Web应用程序的技术堆栈
- swift基本运算符
- vs2010 未能正确加载方案中的一个或多个项目
- SQL SERVER 数据库邮件配置
- Java 编程的动态性,第 8 部分: 用代码生成取代反射--转载
- cdn与http缓存
- JavaScript的事件机制
- pat1071-1080
- Async分析
- AnjularJS 学习
- Spring Boot (五)Spring Data JPA 操作 MySQL 8
- 2017-9-17-Windows Live Writer常用快捷键
- Service Fabric下删除实例并注销应用
- fork和exec