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;
}