2015 Multi-University Training Contest 2 1004 Delicious Apples（DP）-白红宇

2015 Multi-University Training Contest 2 1004 Delicious Apples（DP）

阅读量：6992 次

发布时间：2019-06-27

本文共 1446 字，大约阅读时间需要 4 分钟。

题意：长度为l 的环，有n棵果树，背包容量为k，告诉你k棵苹果树的id。以及每棵树上结的果子数。背包一旦装满要返回起点（id==0)

清空，问你至少走多少路，能摘全然部的苹果。

思路：

由于是环形，所以事实上离起点最远的点应该是l / 2。

两种摘苹果的方式。一种从上半圈開始走。用dp[0][i]记录；

第二种。从下半圈開始走。用dp[1][i]记录；

allv 记录苹果总数，那么仅仅要找出最小的 dp[0][i] + dp[1][all-i]就好啦。

代码例如以下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;typedef long long ll;const int N = 1e5+10;const ll INF = 1E18;ll l, n, k, inf;ll dp[2][N];ll allv;struct node{	ll d, v;	bool operator < (const node &rhs) const{		return d < rhs.d;	}}tree[N];int main(){	int t;	scanf("%d", &t);	while(t--)	{		allv = 0;		scanf("%I64d%I64d%I64d", &l, &n, &k);		for(int i = 0; i < n; i++)		{			scanf("%I64d%I64d", &tree[i].d, &tree[i].v);			allv += tree[i].v;		}		sort(tree, tree + n);		int cnt = 1;		for(int i = 0; i < n; i++)		{			for(int j = 0; j < tree[i].v; j++)			{				int tmp = 0, dis = l;				if(cnt > k)				{					tmp = cnt -k;				}				if(2 * tree[i].d  < l)					dis = 2 * tree[i].d;				dp[0][cnt] = dp[0][tmp] + dis;				cnt ++;			}			}		cnt = 1;		for(int i = n-1; i >= 0; i--)		{			for(int j = 0; j < tree[i].v; j++)			{				int tmp = 0, dis = l;				if(cnt > k)				{					tmp = cnt -k;				}				if((2 * l - 2 * tree[i].d) < l)					dis = 2*l - 2 * tree[i].d;				dp[1][cnt] = dp[1][tmp] + dis;				cnt ++;			}			}		ll ans = INF;		for(int i = 0; i <= allv; i++)		{			ans = min(ans, dp[0][i] + dp[1][allv-i]);		}		printf("%I64d\n", ans);	} 	return 0;}