寒假集訓02 J hdu 5303 DP+枚舉

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=5303

題意：

在一圈長為l的圓圈周圍種了n棵蘋果樹

有一個容積為k的籃子

圓圈的原點是0，順時針方向記錄了蘋果樹的位置以及蘋果的數量

将蘋果全部摘完，最少需要走多少路

籃子裝滿就必須走回原點

題目分析：

對這個環，有3種操作：

1.順時針過去取

2.逆時針過去取

3.繞這個環一圈取

1和2如果走過了環的一半，就變成了3，是以1和2是不能走過環的一半的。

而對于1和2，每次取的k個蘋果，其花費的距離必然為max(xi)*2|i=1,2...k，是以拿的這k個蘋果的距離一定是目前這半環中的最大的k個，因為既然花費距離已定，那不如将這次操作的優化價值提升到最大，也就是每次都盡量消去距離最遠的蘋果。

對于3，同樣，花費一定是L，每次也同樣要消去距離最遠的蘋果。但是，可以發現，如果操作中出現了2次操作3，那麼這個操作一定不是最優的，因為可以通過1和2兩次操作取得兩次操作3獲得的蘋果，且花費更低。是以操作中隻可能出現一次操作3且這次操作3若要發生，一定發生在操作剛開始，因為此時進行操作3的優化價值是最大的。

綜上得到以下解法：

1、先分左邊和右邊分别進行DP，求出最少距離。設dpl[i],dpr[i]分别表示采摘左邊、右邊的第i個蘋果時的最少距離總和。

2、枚舉走一圈情況下的左邊和右邊的蘋果數量，得到距離和上面比較，取最小值。

注意點：

取值範圍取long long, 輸入最好用scanf()

#include <iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
#define N 100005
#define ll long long

int l[N], r[N];
ll dpl[N], dpr[N];
int main()
{
 //freopen("E:\input.txt", "r", stdin);
    int t;
    int L, n, k;
    int i;
    int n1, n2;
    ll sum;
    cin >> t;
    while (t--)
    {
        memset(l, 0, sizeof(l));
        memset(r, 0, sizeof(r));
        memset(dpl, 0, sizeof(dpl));
        memset(dpr, 0, sizeof(dpr));
        n1 = 0;
        n2 = 0;
        sum = 0;
        int x, a;
        cin >> L >> n >> k;
        //scanf("%d%d%d", &L, &n, &k);

        for (i = 0; i < n; i++)
        {
            //cin >> x >> a;
            scanf("%d%d", &x, &a);
            while (a--)
            {
                if (2 * x > L)
                {
                    l[++n1] = L - x;
                }
                else
                {
                    r[++n2] = x;
                }
            }
        }
        sort(l + 1, l + n1 + 1);
        sort(r + 1, r + n2 + 1);
        //sort(x, x + n);
        dpl[0] = 0;
        dpr[0] = 0;
        for (i = 1; i <= n1; i++)
        {
            if (i <= k)
            {
                dpl[i] = l[i];
            }
            else
            {
                dpl[i] = dpl[i - k] + l[i];
            }
        }
        for (i = 1; i <= n2; i++)
        {
            if (i <= k)
            {
                dpr[i] = r[i];
            }
            else
            {
                dpr[i] = dpr[i - k] + r[i];
            }
        }
        sum = 2 * (dpl[n1] + dpr[n2]);

        for (i = 0; i <= min(n1, k); i++) //枚舉走一圈時左邊蘋果的數量
        {
            //k-i為走一圈時右邊蘋果的數量，n2-(k-i)就是右邊原路傳回采摘的蘋果數量
            int j = max(n2 - (k - i), 0);
            最後的結果就是左邊原路傳回方案的花費加上右邊原路傳回的花費，再加上圈長
            sum = min(sum, 2 * (dpl[n1 - i] + dpr[j]) + L);
        }
   // cout << sum << endl;
      printf("%I64d\n", sum);

    }
    return 0;
}
 
           

hdu 5303  相關1

HDU 5303 相關2