Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一道斜率优化,纪念!

Posted by uiu at 2015-08-11 15:25:18 on Problem 1180
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=10000+10;
int n,s,tt[maxn],f[maxn];
double sumt[maxn];
int dp[maxn],q[maxn],sumf[maxn];
int head,t;

void headdelete(int i){
	while (head<t&&(dp[q[head+1]]-dp[q[head]])/(sumt[q[head]-1]-sumt[q[head+1]-1])<=sumf[i]) head++; //不能写<=!!!!!!
}

void taildelete(int i){
	while (head<t&&(dp[i]-dp[q[t]])/(sumt[q[t]-1]-sumt[i-1])<=(dp[q[t]]-dp[q[t-1]])/(sumt[q[t-1]-1]-sumt[q[t]-1]))  t--;
	q[++t]=i;
}

int main()
{
	scanf("%d%d",&n,&s);
	for (int i=1;i<=n;++i) {
		scanf("%d%d",&tt[i],&f[i]);
		sumt[i]=sumt[i-1]+tt[i];
	}
	for (int i=n;i>=1;--i) sumf[i]=sumf[i+1]+f[i];
	dp[n+1]=0; q[1]=n+1;
	head=1; t=1;
	for (int i=n;i>=1;--i){
		headdelete(i);
		dp[i]=dp[q[head]]+(s+sumt[q[head]-1]-sumt[i-1])*sumf[i];
		taildelete(i);
	}
	printf("%d",dp[1]);
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator