题意：一个长为L的圈种上n颗树，每棵树的坐标为xi，结了ai个苹果，用大小为k的篮子把所有苹果装回来，问最少走多少路
解：被神奇的dp教做人了（其实我比较水，本来以为左边贪心一下，，右边贪心一下在最后转一圈就搞定的水题=-=）
#include <stdio.h>#include <string.h>#include <algorithm>#define ll __int64#define MIN(a,b) ((a)<(b)?(a):(b))const int maxn=100005;using namespace std;ll dp[3][maxn];struct aaa{int x,a;}tree[maxn];int cmp(aaa a,aaa b){return a.x<b.x;}int main(){int t;int l,n,k;while(scanf("%d",&t)!=-1){while(t–){scanf("%d%d%d",&l,&n,&k);for(int i=0;i<n;i++)scanf("%d%d",&tree[i].x,&tree[i].a);sort(tree,tree+n,cmp);dp[0][0]=dp[1][0]=0;int fr,ed=1;for(int i=0;i<n;i++)//顺时针每个苹果取到时走的路{for(int j=0;j<tree[i].a;j++){fr=ed-k>0?ed-k:0;dp[0][ed]=dp[0][fr]+(2*tree[i].x>l?l:2*tree[i].x);ed++;}}ed=1;ll sum=0;for(int i=n-1;i>=0;i–)//逆时针每个苹果取到时走的路{sum+=tree[i].a;for(int j=0;j<tree[i].a;j++){fr=ed-k>0?ed-k:0;dp[1][ed]=dp[1][fr]+(2*(l-tree[i].x)>l?l:2*(l-tree[i].x));ed++;}}ll lenth=1000000000;for(ll i=0;i<=sum;i++)lenth=MIN(lenth,dp[0][i]+dp[1][sum-i]); //找最小的printf("%I64d\n",lenth);}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
你曾经说，等我们老的时候，
