poj 2355

还是思维不够灵活，刚开始，只想到了那个O(n3)的算法，知道肯定不行，苦苦思索，实在想不出来，浏览了一下其他人的博客，刚扫一眼，突然想到了还是从最优解的最后的状态考虑，得到了O(n2)的算法，就是对于节点i，枚举，在他左边的与他举例小于l3的点，得到状态转移方程f[i]=min(f[j]+cost)，ac之，然后看了浩神的博客，还可以用二分优化，想了想，确实可以，因为点到s起点的举例是单调非减的，对于同一段的肯定最左边的最优，二分得之

#include <iostream>
#include <cstdio>
#define LL __int64
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int maxn=10000+10;
const int inf=0x3f3f3f3f;
int l1,l2,l3,c1,c2,c3,n,s,e;
int dis[maxn];
int f[maxn];
int search(int de,int cm,int cost)
{
	int l=s,r=de,mid;
	while(r-l>0)
	{
		mid=l+(r-l)/2;
		if((dis[de]-dis[mid])<=cm) r=mid;
		else l=mid+1;
	}
	return f[r]+cost;
}
int main()
{
	while(~scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3))
	{
		scanf("%d",&n);
		scanf("%d%d",&s,&e);
		int  tem;
		if(s>e)
		{
			tem=s;
			s=e;
			e=tem;
		}
		int i,j;
		for(i=2;i<=n;i++) scanf("%d",&dis[i]);
		f[s]=0;
		for(i=s+1;i<=e;i++)
		{
			f[i]=inf;
			f[i]=min(f[i],search(i,l1,c1));
			f[i]=min(f[i],search(i,l2,c2));
			f[i]=min(f[i],search(i,l3,c3));
		}
		printf("%d\n",f[e]);
	}
	return 0;
}