题意：

在一个长度为L的环上有N棵苹果树。你的篮子容量是K个苹果。

每棵苹果树上都有a[i]个苹果。

问你从0点出发最少要走多少距离能拿完所有的苹果。

思路：

我们考虑dp，dp[0][i]代表顺时针取i个苹果的最短距离。

dp[1][i]代表逆时针取i个苹果的最短距离。

那么设苹果的总是为sum

那么ans=dp[0][i]+dp[sum-i]  (0<=i<=sum)

代码：

#include"stdio.h"#include"algorithm"#include"string.h"#include"iostream"#include"queue"#include"map"#include"vector"#include"string"#include"cmath"using namespace std;#define ll __int64ll l;struct node{ int x,s;} ap[123456];ll dp[2][123456];int cmp(node a,node b){ return a.x<b.x;}int main(){ int t; cin>>t; while(t--) { int n,k; scanf("%I64d%d%d",&l,&n,&k); for(int i=0; i<n; i++) scanf("%d%d",&ap[i].x,&ap[i].s); memset(dp,0,sizeof(dp)); sort(ap,ap+n,cmp); int tep=1,sum=0; //tep代表取了几个苹果 由于一定是递增的 for(int i=0; i<n; i++) { for(int j=0; j<ap[i].s; j++) { if(tep-k<0) dp[0][tep]=dp[0][0]+min(l,2LL*ap[i].x); else dp[0][tep]=dp[0][tep-k]+min(l,2LL*ap[i].x); tep++; } } tep=1; for(int i=n-1; i>=0; i--) { sum+=ap[i].s; for(int j=0; j<ap[i].s; j++) { if(tep-k<0) dp[1][tep]=dp[1][0]+min(l,2LL*(l-ap[i].x)); else dp[1][tep]=dp[1][tep-k]+min(l,2LL*(l-ap[i].x)); tep++; } } ll ans=999999999999999999LL; for(int i=0;i<=sum;i++) ans=min(ans,dp[0][i]+dp[1][sum-i]); printf("%I64d\n",ans); } return 0;}