[ZOJ 3469]Food Delivery[记忆化搜索]

时间:2022-06-26 04:29:51
题目链接: [ZOJ 3469]Food Delivery[记忆化搜索]

题意分析:

送餐员需要从X处餐厅出发,去给顾客送食物,送餐员经过客户门口即可选择是否提交食物(所有食物已经都存放在外卖小哥手上了)。每个顾客随着等待时间的上升都会产生戾气,戾气值为bi每分钟,现在外卖员以V的-1次方米每分钟的速度送餐(也就是每米V分钟),问:最少造成的戾气值为多少?

解题思路:

设状态dp[i][j][sta]为外卖员送完区间[i,j]最少造成的戾气,sta为0代表此时外卖员在区间左边,1代表在右边。

那么dp[i][j][0]只可能由dp[i + 1][j]而来,dp[i][j][1]只可能由dp[i][j - 1]而来。根据这个转移即可。

个人感受:

虽然比赛时没做出来,卡在怎么处理戾气值上。不过这种区间DP如今已经没那么恶心了,2333

具体代码如下:

#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<string>
#define ll long long
#define pr(x) cout << #x << " = " << (x) << '\n';
using namespace std;

const int MAXN = 1e3 + 11;

ll dp[MAXN][MAXN][2];
struct P {
    ll x, b;
    bool operator < (const P &t)const {
        return x < t.x;
    }
}a[MAXN];

int n;
ll X, v, sum[MAXN];

ll dfs(ll l, ll r, int sta) {
    ll &ret = dp[l][r][sta];

    if (ret >= 0) return ret;
    if (l == r) return ret = abs((X - a[l].x)) * v * sum[n];

    if (sta == 0) {
        ll mul = sum[l] + sum[n] - sum[r];
        ret = min(dfs(l + 1, r, 0) + (a[l + 1].x - a[l].x) * v * mul,
                  dfs(l + 1, r, 1) + (a[r].x - a[l].x) * v * mul);
    }
    else {
        ll mul = sum[l - 1] + sum[n] - sum[r - 1];
        ret = min(dfs(l, r - 1, 1) + (a[r].x - a[r - 1].x) * v * mul,
                  dfs(l, r - 1, 0) + (a[r].x - a[l].x) * v * mul);
    }

    return ret;
}

int main()
{
    while (~scanf("%d%d%lld", &n, &v, &X)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld%lld", &a[i].x, &a[i].b);
        }
        sort(a + 1, a + n + 1);

        sum[0] = 0;
        for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + a[i].b;
        memset(dp, -1, sizeof dp);
        printf("%lld\n", min(dfs(1, n, 0), dfs(1, n, 1)));
    }
    return 0;
}