首页 > 代码库 > HDU 3507

HDU 3507

2024-08-07 05:19:45   218人阅读

斜率DP入门题。推荐看看这篇http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

 

看过之后，自己思考，发现有些不妥之处就是，其实CI必须为正数才能保证SUM【i】的那个比较条件是成立的，才能使用单调队列维护，没有这个条件，是不成立的。也算是自己一个发现了。

 

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#define N 500050using namespace std;int dp[N],su[N],q[N+100];int head,tail;int UP(int j,int k){	return dp[j]+su[j]*su[j]-dp[k]-su[k]*su[k];}int DOWN (int j,int k){	return 2*su[j]-2*su[k];}int main(){	int n,m,tmp;	su[0]=0;	while(scanf("%d%d",&n,&m)!=EOF){		head=tail=0;		for(int i=1;i<=n;i++){			scanf("%d",&tmp);			su[i]=tmp+su[i-1];		}		memset(dp,0,sizeof(dp));		q[0]=0; tail=1;		for(int i=1;i<=n;i++){			while(head<tail-1&&UP(q[head+1],q[head])<=DOWN(q[head+1],q[head])*su[i])			head++;			dp[i]=dp[q[head]]+(su[i]-su[q[head]])*(su[i]-su[q[head]])+m;			while(head<tail-1&&UP(i,q[tail-1])*DOWN(q[tail-1],q[tail-2])<=UP(q[tail-1],q[tail-2])*DOWN(i,q[tail-1]))			tail--;			q[tail++]=i;		}		printf("%d\n",dp[n]);	}	return 0;}

　　

HDU 3507


联系
我们