zoj 3469 dp 记忆化搜索

/*zoj 3469
  记忆化dp；
  dp[i][j][0-1]表示已经送过左边的i个和右边的j个，01分别表示当前停在那里
key2:当前要走的距离也是其之后要送的走的距离·
参照大牛写的，orz，dp的路还很长啊
*/


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
//#define min(a,b) ((a)<(b))?((a):(b))
#define inf 0x3ffffffffff
using namespace std;


struct abc
{
	int x;
	int b; 
}lef[1010],righ[1010];


int l,r;


bool cmp(abc a,abc b)
{
	return a.x<b.x;
}




long long dp[1010][1010][2];
//int len[1010][1010][2];


long long  getdp(int i,int j,int k)
{
	if(dp[i][j][k]!=-1)return dp[i][j][k];
	long long ans=inf;
	if(k==0)//在左边
	{
		if(i!=0)
		{
			int tmp=lef[i].b+righ[j+1].b;//所有还未走的的人的愤怒值之和
			ans=min(ans,getdp(i-1,j,0)+(lef[i].x-lef[i-1].x)*tmp);
			ans=min(ans,getdp(i-1,j,1)+(lef[i].x+righ[j].x)*tmp);
		}
	}
	else 
	{
		if(j!=0)
		{
			int tmp=lef[i+1].b+righ[j].b;
			ans=min(ans,getdp(i,j-1,1)+(righ[j].x-righ[j-1].x)*tmp);
			ans=min(ans,getdp(i,j-1,0)+(lef[i].x+righ[j].x)*tmp);
		}
	}
	return dp[i][j][k]=ans;
}


int main()
{
	int n,v,x;
	while(scanf("%d%d%d",&n,&v,&x)!=EOF)
	{
		int tx,tb;
		l=r=1;
		for(int i=0;i<n;i++)
		{
			scanf("%d%d",&tx,&tb);
			if(tx>x)
			{
				righ[r].x=tx-x;righ[r].b=tb;r++;
			}
			else 
			{
				lef[l].x=x-tx;lef[l].b=tb;l++;
			}
		}
		sort(righ+1,righ+r,cmp);
		sort(lef+1,lef+l,cmp);
		righ[r].b=0;lef[l].b=0;
		for(int i=r-1;i>=1;i--)
		{
			righ[i].b+=righ[i+1].b;
		}

		for(int i=l-1;i>=1;i--)
		{
			lef[i].b+=lef[i+1].b;
			// cout<<lef[i].b<<' ';
		}
		// cout<<endl;
		for(int i=0;i<=l;i++)
			for(int j=0;j<=r;j++)
			{
				dp[i][j][0]=dp[i][j][1]=-1;
			}
		dp[0][0][0]=dp[0][0][1]=0;
		// cout<<"asdasd"<<endl;
		printf("%lld\n",v*min(getdp(l-1,r-1,0),getdp(l-1,r-1,1)));
	}
	return 0;
}