Code 備忘錄►DP

TIOJ::IOI::1884 . 【IOI2015】Boxes 一堆盒子

http://tioj.ck.tp.edu.tw/problems/1884

這題應該是IOI 2015 Day1裡最簡單的。
用一些DP技巧就可以解出來。

題目給你一個環，編號從0到L-1，L-1後面循環到0，還有n個隊伍，每個隊伍可能在0到L-1之間的任何一個位置。
現在你要發禮物，你一次可以拿K個（小於等於隊伍數量n），在環上移動一格需要1秒，你發完後要再回到0拿k個繼續發，問你最後發完全部人再會到0的最少時間是多少。

觀察一下，可以確定，你最多只需要繞一整圈一次，其他時候你都可以只走左半邊或右半邊來發完禮物，（你發完左邊的禮物後如果手上還有代表你已經發完左邊了，然後你才會去發右邊，如果你還沒發完，那你乾脆發完然後從左邊回去會比較快）。所以我們先看看所有的隊伍在的位置（題目已經幫你排好序），把他分成兩堆，一堆在圓環左半邊，一堆是右半邊，兩堆可能不一樣大喔。
設兩個陣列L[i]、R[j]，代表從0開始到左、右半邊的第i、j個隊伍，所需要的最少發禮物時間。
DP轉移式就是：
L[i] = L[i-k] + P[i] * 2，其中P[i]是那一隊到0的最短距離，當i-k小於0的時候L[i-k]都是0，右邊一樣，就不寫了。

然後，我們要考慮兩種狀況，一種是我只在左邊和右邊發完禮物就好了，一種是我最後一次繞一圈比較快。
所以答案就是L[n_l] + R[n_r] 和對於 i 從 0 到 k 取 min(L[n_l-i] + R[n_r-k+i]) + l，這兩個中比較小的那個就是答案。其中 n_l、n_r 是兩邊的隊伍數量，l 是一圈的長度，後面那個的意思就是留下中間的k個隊伍然後最後一次繞一圈發完。

這題還有一點比較有趣的是，因為輸入太大了，輸入優化效果很好，而且這次用了一個新的輸入優化，就是自訂一個函數readchar()，然後用fread一次吃一堆bytes進來，先用陣列存起來，再一次傳一個回去，這樣可以快4秒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1e7+3;
long long L[N],R[N];
int D[N];
inline int readchar() {
    const int N = 1048576;
    static char buf[N];
    static char *p = buf, *end = buf;
    if(p == end) {
        if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
        p = buf;
    }
    return *p++;
}
template<typename T>
inline bool gin(T &x){
    char c=0;bool flag=0;
    while(c=readchar(),c<'0'&&c!='-'||c>'9')if(c==-1)return false;
    c=='-'?(flag=1,x=0):(x=c-'0');
    while(c=readchar(),c>='0'&&c<='9')x=x*10+c-'0';
    if(flag)x=-x;
    return true;
}
template<typename T, typename ...Args>
inline bool gin(T &x, Args &...args){
    return gin(x)&&gin(args...);
}
main(){
    int t,n,k,l;
    gin(t);
    while(t--){
        gin(n,k,l);
        F(n)gin(D[i]);
        int mid = 0;
        while(mid < n && D[mid] <= l/2){
            R[mid+1] = 2*D[mid];
            if(mid+1-k>0)R[mid+1] += R[mid+1-k];
            mid++;
        }
        F(n-mid){
            L[i+1] = 2*(l-D[n-1-i]);
            if(i+1-k>0)L[i+1] += L[i+1-k];
        }
        long long ans = R[mid] + L[n-mid];
        F(k+1){
            long long tmp = l;
            if(mid-i>0)tmp += R[mid-i];
            if(n-mid-k+i>0)tmp += L[n-mid-k+i];
            if(tmp<ans)ans=tmp;
        }
        printf("%lld\n",ans);
    }
}