#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define N 10005
#define inf 999999999

__int64 max(__int64 a,__int64 b){return a>b?a:b;}
__int64 min(__int64 a,__int64 b){return a<b?a:b;}

struct node{
	__int64 x, y;
}a[N];

int n, d;
main()
{
	int i, j, k;
	int maxh, minh;
	while(scanf("%d %d",&n,&d)==2){
		maxh=-1;
		for(i=0;i<n;i++){
			scanf("%I64d %I64d",&a[i].x,&a[i].y);
			maxh=max(maxh,a[i].x);
			minh=min(minh,a[i].x);
		}
		maxh=(maxh-minh)/d;
		__int64 ans=a[0].x*a[0].y;
		for(i=1;i<n;i++){
			int v=-1;
			for(j=i-1;j>=0;j--){
				if(i-j>maxh) break;      //起码需要往前找maxh个，再往前面找就没有意义了
				int aa=(a[i].x-a[j].x)/(i-j);//初略估计时间复杂度最多为5000*4999/2+5000^2<5000W   不会超时 
				if(v<aa&&d<aa){
					v=aa;
					k=j;
				}
			}
			if(v!=-1) ans+=a[k].x*a[i].y+a[i].y*(__int64)(d*(i-k));
			else ans+=a[i].x*a[i].y;
		}
		printf("%I64d\n",ans);
	}
}

• Re:检查相邻的肯定错了。。。贴个正确的代码 (1121) lunning 2015-07-17 13:44:10