hdu4412 Sky Soldiers 动态规划杭州网赛的第三题

9月 16

题目大意是有k个伞兵落到地面上，已知每个人落点的概率，有m个物资站，落地后要去最近的站。问如何安排这些物资站，使得伞兵落地后行走的期望距离的和最小。（所有落点最多1000个）。

显然是个dp题，我们可以先预处理下，对每个落点点求出他的概率总和，代表伞兵落在这点的权。可以直到物资站一定悬在伞兵落下的那些点上，所以我们就可以用 $dp_{ij}$ 表示前 $i$ 个落地点中选择 $j$ 个作为物资点，则很容易想到转移方程 $dp_{ij}=min(dp_{kj_{1}}+dis_{ki})$ ，其中 $j_{1}=j+1$ , $dis_{ki}$ 表示在 $[k,i]$ 区间的落地点选则一个作为物资点所走距离最小值的期望(就是每点到物资点的距离乘该点概率的总和)。

现在关键就是求 $dis$ ，其实我们注意到假设对于 $[i,j]$ ，假设选取 $k$ 作为物资点，则有

$dis_{ij}=\sum_{n=i}^{k}{(a_{k}-a_{n})p_{n}} + \sum_{n=k+1}^{j}{(a_{n}-a_{k})p_{n}}$

而若选择 $k+1$ 作为物资点，则有

$dis_{ij}^{‘}=\sum_{n=i}^{k}{(a_{k+1}-a_{n})p_{n}} + \sum_{n=k+1}^{j}{(a_{n}-a_{k+1})p_{n}}$

则相减并化简得

$dis_{ij}^{‘}-dis_{ij}= (a_{k_{1}}-a_{k})(\sum_{n=i}^{k}{p_{n}} - \sum_{n=k+1}^{j}{p_{n}}) = (a_{k_{1}}-a_{k})(sum_{ik}-sum_{k_{1}{j}})$

设 $tmp=dis_{ij}^{‘}-dis_{ij}$ , $sum$ 可以很容易求出，这样很显然，当 $k$ 增加时， $tmp$ 的值也在增加，所以，若选取 $k$ 作为物资点，则要 $tmp \geq 0$ ，否则我们可以选取 $k+1$ 作为物资点，这样，可以对 $dis$ 进行预处理，然后就可以得出答案

hdu4412 Sky Soldiersview raw

#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

struct prog{
	double p;
	int k;
}pos[1005];
bool cmp(prog a,prog b)
{
	return a.k<b.k;
}
double dis[1005][1005];
double sum[1005][1005];
double dp[1005][1005];
int main()
{
	int kx,m;
	while(scanf("%d%d",&kx,&m),kx||m)
	{
		int i,j,k;
		int pos_num=0;
		map<int,int>mp;

		for(i=0;i<kx;i++)
		{
			int n;
			scanf("%d",&n);
			//cout<<1<<endl;
			for(j=0;j<n;j++)
			{
				int t;
				double p;
				scanf("%d%lf",&t,&p);
				if(mp.count(t)==0)
				{
					mp[t]=pos_num;
					pos[pos_num].p=p;
					pos[pos_num++].k=t;
				}
				else
				{
					pos[mp[t]].p+=p;
				}
			}
		}

		sort(pos,pos+pos_num,cmp);

		zero(sum);
		for(i=0;i<pos_num;i++)
		{
			sum[i][i]=pos[i].p;
			for(j=i+1;j<pos_num;j++)
			{
				sum[i][j]=sum[i][j-1]+pos[j].p;
			}
		}

		zero(dis);
		for(i=0;i<pos_num;i++)
		{
			for(j=i+1;j<pos_num;j++)
			{
				dis[i][j]=0.0;
				for(k=i+1;k<=j;k++)
				{
					dis[i][j]+=(pos[k].k-pos[i].k)*pos[k].p;
				}

				double tmp=dis[i][j];
				for(k=i+1;k<=j;k++)
				{
					tmp=(pos[k].k-pos[k-1].k)*(sum[i][k-1]-sum[k][j])+dis[i][j];
					if(tmp<dis[i][j])
						dis[i][j]=tmp;
					else
						break;
				}
				//cout<<dis[i][j]<<endl;
			}
		}

		for(i=0;i<pos_num;i++)
		{
			//dp[i][0]=0;
			dp[i][1]=dis[0][i];
			for(j=2;j<=m;j++)
			{
				dp[i][j]=1000000000.0;
				for(k=0;k<=i;k++)
				{
					dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]);
				}
			}
		}

		printf("%.2lf\n",dp[pos_num-1][m]);
	}
    return 0;
}