题意大概就是有n框苹果放在长度为L的环上，每框有ai个苹果，，你有一个容量为k的框，要你从0点处出发，任意走，框满了就回到0点把苹果放在那里，继续走直到把苹果都拿完为止，问你最少要走多少路程。
首先贪心的策略，不管往哪边走，碰到苹果就拿，拿满就滚回去。
然后碰到走一个半圈，框还剩下容量的情况，就需要dp了，主要是L为偶数的时候，若L/2的位置有苹果，该算是哪个半圈拿比较好呢？
当然也可以继续贪心，然而太麻烦了。直接dp。
并且由此贪心可以知道若存在需要走一圈的情况，肯定最多走一次一圈。
我们把苹果的位置当作它的权值，全部铺在环上。
dp[0][j]:左半圈拿完j位置的苹果就回去的最小代价
dp[1][j]:右半圈拿完j位置的苹果就回去的最小代价
很显然，dp[i][j]=dp[i][j-k]+val[j]
最后再枚举走一圈的时候，从左半圈的底部拿走几个苹果，从右半圈的底部拿走几个苹果，不断更新ans即可。
具体看代码吧，很容易懂。
#include<map>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<vector>#include<iostream>#include<algorithm>#include<bitset>#include<climits>#include<list>#include<iomanip>#include<stack>#include<set>using namespace std;typedef long long ll;int a[2][100010],len[2];ll dp[2][100010];int main(){int T;cin>>T;while(T–){memset(len,0,sizeof(len));int l,n,k;scanf("%d%d%d",&l,&n,&k);int m=l>>1;while(n–){int x,t;scanf("%d%d",&x,&t);int i=0;if(x>m){i=1;x=l-x;}while(t–)a[i][++len[i]]=x;}for(int i=0;i<2;i++)sort(a[i],a[i]+len[i]+1);for(int i=0;i<2;i++)for(int j=0;j<=len[i];j++){dp[i][j]=a[i][j];if(j>=k)dp[i][j]+=dp[i][j-k];}ll ans=dp[0][len[0]]+dp[1][len[1]]<<1;for(int i=0;i<=k&&i<=len[0];i++)ans=min(ans,2*(dp[0][len[0]-i]+dp[1][max(0,len[1]-(k-i))])+l);cout<<ans<<endl;}}
Time Limit: 5000/3000 MS (Java/Others)Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1078Accepted Submission(s): 358
Problem Description
There areapple trees planted along a cyclic road, which ismetres long. Your storehouse is built at positionon that cyclic road.Theth tree is planted at position, clockwise from position. There aredelicious apple(s) on theth tree.You only have a basket which can contain at mostapple(s). You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line:, the number of testcases.Thentestcases follow. In each testcase:First line contains three integers,.Nextlines, each line contains.
Output
Output total distance in a line for each testcase.
Sample Input
210 3 22 28 25 110 4 12 28 25 10 10000
Sample Output
1826
Source
版权声明：本文为博主原创文章，未经博主允许不得转载。
感悟了不同的人生。凌晨，随着滑轮接触地面，
