2017女生赛--HDU-6024（简单dp）

HDU--6024（简单DP）

搜了搜题解 ， 全是说这题是个简单DP的 ， 然鹅。。。。。。。我看了好久好久好久。。。。。。。。。。

题意：

在一条路上散布着多个房子 ， 每个房子可以选择建或不建糖果屋。满足以下条件：

1. 建糖果屋 ， 需要花费cost[i]
2. 不建糖果屋 ， 需要花费该点到其左边最近的一个糖果屋之间的距离

（左边第一个房子一定建糖果屋）

问最小花费。

令dp[i][j]表示前i个的最小花费。I 为当前点 ， j = 0 表示不建 ， j = 1 表示建。

1. 建的情况

如果在第i点建 ， 那他一定是由上一个点建或不建的最小值加上他当前的cost[i]

所以转移式为：

Dp[i][1] = min( dp[i-1][0]  ,  dp[i-1][1] )  +  cost[i];

1. 不建的情况。

如果在第i点不建 ， 那他需要加上该点到上一个建了的点（k）之间的距离

K 一定是小于i的，并且数据范围是3e3可以O（n^2）.那么就可以每次从1到 i-1 暴力求不建时的最小值。

3.

最后解决暴力时俩点之间的距离问题。

     1            3                6

比如求6到1 的距离 ， 并且3这个点也没有建，所以也得加上3到1的距离

也就是 dis[6][1] + dis[3][1]

可以转化为  dis[6][3] + 2*dis[3][1];

所以这样一段代码提前预处理一下。

void init()
{
	for(int i = 1 ; i <= n ; i++)
	{
		ll t = 0;
		for(int j = i+1 ; j <= n ; j++)
		{
			t += (a[j].num-a[i].num);
			dis[j][i] = t;
		}
	}
}

代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
const int maxn = 3e3+8;
struct node 
{
	ll num;
	ll cost;
}a[maxn];
ll dis[maxn][maxn];
ll dp[maxn][2];
int n;
void init()
{
	for(int i = 1 ; i <= n ; i++)
	{
		ll t = 0;
		for(int j = i+1 ; j <= n ; j++)
		{
			t += (a[j].num-a[i].num);
			dis[j][i] = t;
		}
	}
}
int cmp(node a , node b)
{
	return a.num < b.num;
}
int main()
{
	while(~scanf("%d" , &n))
	{
		memset(dp , INF , sizeof(dp));
		for(int i = 1 ; i <= n ; i++)
		{
			scanf("%lld %lld" , &a[i].num , &a[i].cost);
		}
		sort(a+1 , a+1+n , cmp);
		init();
		dp[1][1] = a[1].cost;
		for(int i = 2 ; i <= n ; i++)
		{
			dp[i][1] = min(dp[i-1][1] , dp[i-1][0]) + a[i].cost;
			for(int j = 1 ; j < i ; j++)
			{
				dp[i][0] = min(dp[i][0] , dp[j][1] +dis[i][j]);
			}
		}
		ll ans = min(dp[n][1] , dp[n][0]);
		printf("%lld\n" , ans);
	}

	
	return 0;
}