Let's Go Rolling! CodeForces - 38E

http://codeforces.com/problemset/problem/38/E

数轴上有一些点，开始会向左边滚动，最终花费等于每个点滚过的距离，每个点还可以花费相应的数值来插上一个挡板，后面的点滚到该点则会停下，求最终的最小花费。

dp。

先按位置前后排序

dp[i][j]代表第i个点在第j个点停下了，当然有j<=i;

对于当前这个点，如果在自己这个点停下，则去前面的点在前一个点停下和在自己这个点停下的最小花费，如果在后面的点停下，则去前面的点也在该点停下和前面的点在前一个点停下的最小值加上自己滚到后面相应的点的花费

具体看代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,cost;
}p[3333];
long long dp[3333][3333];
bool cp(node x1,node y)
{
	return x1.x<y.x;
}
int main(){
	int n,l;
	while(cin>>n){
		memset(dp,0,sizeof(dp));
		for(int i=0;i<n;i++)
		{
			cin>>p[i].x>>p[i].cost;
		}
		sort(p,p+n,cp);
		for(int i=0;i<n-1;i++)
		dp[n-1][i]=p[n-1].x-p[i].x;
		dp[n-1][n-1]=p[n-1].cost;
		for(int i=n-2;i>=0;i--)
		{
			for(int j=i;j>=0;j--)
			{
				if(i==j)
				{
					dp[i][j]=min(dp[i+1][j+1],dp[i+1][j])+p[i].cost;
				}
				else 
				dp[i][j]=min(dp[i+1][j]+p[i].x-p[j].x,dp[i+1][i+1]+p[i].x-p[j].x);
			}
		}
		
		/*for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cout<<dp[i][j]<<' ';
			}
			cout<<endl;
		}*/
		
		cout<<dp[0][0]<<endl;
	}
	return 0;
}