题意大概就是有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就可以。
详细看代码吧。非常easy懂。
#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): 1078 Accepted Submission(s): 358
Problem Description
There are n apple
trees planted along a cyclic road, which is L metres
long. Your storehouse is built at position 0 on
that cyclic road.
The ith
tree is planted at position xi,
clockwise from position 0.
There are ai delicious
apple(s) on the ith
tree.
You only have a basket which can contain at most K apple(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?
1≤n,k≤105,ai≥1,a1+a2+...+an≤105
1≤L≤109
0≤x[i]≤L
There are less than 20 huge testcases, and less than 500 small testcases.
trees planted along a cyclic road, which is L metres
long. Your storehouse is built at position 0 on
that cyclic road.
The ith
tree is planted at position xi,
clockwise from position 0.
There are ai delicious
apple(s) on the ith
tree.
You only have a basket which can contain at most K apple(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?
1≤n,k≤105,ai≥1,a1+a2+...+an≤105
1≤L≤109
0≤x[i]≤L
There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line: t,
the number of testcases.
Then t testcases
follow. In each testcase:
First line contains three integers, L,n,K.
Next n lines,
each line contains xi,ai.
the number of testcases.
Then t testcases
follow. In each testcase:
First line contains three integers, L,n,K.
Next n lines,
each line contains xi,ai.
Output
Output total distance in a line for each testcase.
Sample Input
2
10 3 2
2 2
8 2
5 1
10 4 1
2 2
8 2
5 1
0 10000
Sample Output
18
26
Source