hdu 5303 Delicious Apples 2015多校合同訓練試合2 dp+列挙

Delicious Apples
Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 311    Accepted Submission(s): 92
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 
i th tree is planted at position 
xi , clockwise from position 
0 . There are 
ai  delicious apple(s) on the 
i th 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 .
 
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
2015 Multi-University Training Contest 2
タイトル:
輪があって、輪の上で異なる位置に一定数のリンゴがあって、リンゴは起点と距離があります.初期位置は0時です.バスケットがあって、毎回K個のりんごを入れることができます.すべてのりんごをかごで起点まで詰めて、少なくともどのくらいの距離を歩かなければなりませんか.
分析:
りんごの総数<=100000.では、りんごごとに順番に並べ替えます.
時計回りと反時計回りに分けて処理します.
dp[0][i]は、針に沿って前に進むしかなく、反時計回りに起点に戻ることを示す.時計回りの前のi個のリンゴを原点に持ち帰る最小の道のり
            ではdp[0][i]=dp[0][i-K]+2*dist[i]  -----------dist[i]は、i番目のリンゴが時計回りに起点から離れる距離を表す
同理反時計回りの転移方程式は
           dp[1][i] = dp[1][i+K] + 2*(L-dist[i])
そしてi番目のリンゴを列挙するのは境界線で、i個のリンゴと前のリンゴは時計回りに取得し、i+1と後のリンゴは反時計回りに取得します
         ではans=min(ans,dp[0][i]+dp[1][i+1])
しかし、このような場合、i番目のりんごを取ったとき、元の道に戻さず、2つ目は直接ゴールまで歩いた.
       ではans=min(ans,dp[0][i-K]+dp[1][i+1]+L)
最後にansが答え
  

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define maxn 100007
struct Point{
    int x;
    int num;
};
Point p[100007];
Point px[maxn];
int cmp(Point a,Point b){
    return a.x < b.x;
}
ll dp[2][maxn];
int main(){
    int t,L,n,K;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&L,&n,&K);
        int cnt = 1,x,y;
        for(int i = 0;i < n; i++){
            scanf("%d%d",&px[i].x,&px[i].num);
        }
        sort(px,px+n,cmp);
        for(int i = 0;i < n; i++){
            while(px[i].num--){
                p[cnt++].x = px[i].x;
            }
        }
        memset(dp[0],0,sizeof(ll)*(cnt+3));
        memset(dp[1],0,sizeof(ll)*(cnt+3));
        for(int i = 1;i < cnt; i++){
            dp[0][i] = dp[0][max(0,i-K)] + p[i].x * 2;
        }
        for(int i = cnt-1;i > 0; i--){
            dp[1][i] = dp[1][min(cnt,i+K)] + (L - p[i].x) * 2;
        }
        ll ans = min(dp[0][cnt-1],dp[1][1]);
        for(int i = 1;i < cnt; i++){
            ans = min(ans,dp[0][i]+dp[1][i+1]);
            ans = min(ans,dp[0][max(0,i-K)] + dp[1][i+1] + L);
        }
        printf("%I64d
",ans);
    }
    return 0;
}