Skip to content

14112: 【原4112】Spice and Wolf

题目

题目描述

author: 黄俊翔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4112 ## Description

赫萝与罗伦斯正在米隆商行进口香辛料(胡椒),准备运到帕兹欧去卖掉。来自帕兹欧的订单需求精确的分成了每种品质的胡椒各需多少颗,罗伦斯也准备了相应的本金。但在购买时,赫萝发现了一个问题:每种胡椒需要分开放置,而出于防止变质和尊贵身份防伪标识的考虑——毕竟中世纪的胡椒价值超过等重黄金,按颗计价——每种都需要不同的特制容器保存(容器价格为该品质的胡椒10颗,而且容器的容量可以视为无限大,毕竟胡椒很小);而计算入容器的包装价格之后,严格按照订单购买反而会浪费很多包装费。也就是说,购买同一类的高质量胡椒,甚至可能会比按原订单购买总颗数相同而质量不同的胡椒来的更加省钱。

更少的钱能买到更高质量的胡椒当然是好事(省钱的同时还能卖客户人情),因此赫萝希望你计算出,在满足原订单要求的前提下(允许任意颗胡椒的质量被提升,不允许质量降低),最少的花费为多少枚铜币。

Input Format

第一行包含一个正整数\(T\),为测试数据的组数。

每组测试数据的第一行为一个正整数\(N\),代表胡椒的质量总共有多少类。

接下来\(N\)行,每行两个非负整数\(a_i, p_i\),其中\(a_i\)表示第\(i\)类胡椒收到的订单需求为多少颗,\(p_i\)表示第\(i\)类胡椒每颗的价格为多少枚铜币。如果你决定购买第\(i\)类胡椒,就必须额外支付相当于10颗第\(i\)类胡椒价格的钱用于包装。数据保证随着\(i\)的增大,每颗胡椒的价格单调上升,也代表类编号\(i\)越大的胡椒质量就越高。

Output Format

每组测试数据对应输出一行,代表最少需要花费多少枚铜币才能够满足客户的需求。

Sample Input

2
2
100 15
100 20
3
1 16
1 18
100 20

Sample Output

3850
2240

数据解释:直观上就可以感受出,第一组数据应该按原订单要求购买(提升100颗胡椒的质量所需金钱高于节省下的包装费),而第二组数据应该把质量低的两颗胡椒用质量更高的两颗代替来节省包装费。

Data Range

对于\(40\%\)的数据,\(N \le 15\)。

对于\(100\%\)的数据,\(T \le 10\),\(N \le 1000\),\(a_i \le 1000\),\(p_i \le 2000\)。(记得手动计算下是否有\(MAX(N) \times MAX(a_i) \times MAX(p_i) \le 2147483647\))。

P.S. 尽管从数据解释看起来,似乎是有着某种特判(指特殊判定方法。拿此题打比方的话,一个例子是当购买量小于10颗时就改成提升质量)的做法,或者贪心、找规律、数学方法就可以拿到满分。但为了降低难度起见(防止大家想歪),提前声明一下:此题的正确做法并非上面说的这些策略,当然也不是搜索或者用线段树维护某个值。

P.P.S. 防止掉坑起见,再写一点考(pian)场(fen)策略吧,如果长时间没想出正解或者有空的人可以看一看。

尽管特判或者数学方法对于某些甚至大多数的数据是的确可以通过的,但只要是特判(对于正解不是特判的题来说),就必然存在数据可以卡掉。如果题目是单组数据,这样骗分其实是相当可行的(有时暴力只能稳定30分,但如果出题人数据出的不好就能够特判70分甚至100分);然而在题目为多组数据的保护下,每个测试点的通过率就会指数级降低,这也是多组数据的重要意义之一。

不过一如既往的,暴力搜索可以骗到部分分。然而,并非所有的暴力在任何情况下都值得写——比如此题的暴力就写起来比正解还要长,因为正解太短了(富有经验的选手大多在还未想出正解细节的情况下,就能感受出正解的长短)。如果你其他两题都做完/暴力写完了,而且这题怎么想也想不出正解(比如干想了超过半小时),此时写暴力仍然是很值的。如果不是这样的话,就把时间用在别的地方,或者多想想正解吧。

FineArtz's solution

/* Spice and Wolf */
#include <iostream>
#include <cstring>
using namespace std;

int t, n;
long long a[1005], p[1005], f[1005], s[1005];

int main(){
    cin >> t;
    while (t--){
        memset(a, 0, sizeof(a));
        memset(p, 0, sizeof(p));
        memset(f, 0, sizeof(f));
        memset(s, 0, sizeof(s));
        cin >> n;
        for (int i = 1; i <= n; ++i){
            cin >> a[i] >> p[i];
            s[i] = a[i] + s[i - 1];
        }
        f[1] = (a[1] + 10) * p[1];
        for (int i = 2; i <= n; ++i){
            f[i] = 2147483647;
            for (int j = 0; j < i; ++j){
                f[i] = min(f[i], f[j] + (s[i] - s[j] + 10) * p[i]);
            }
        }
        cout << f[n] << endl;
    }
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
int dp[1001][1001],a[1001],p[1001],t,n,minn;
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i)
    {
        scanf("%d",&n);
        for (int j=n-1;j>=0;--j) scanf("%d%d",&a[j],&p[j]);
        dp[0][0]=a[0]*p[0]+10*p[0];
        for (int j=1;j<n;++j)
        {
            minn=2100000000;
            for (int k=0;k<=j-1;++k) {
                dp[j][k] = dp[j - 1][k] + a[j] * p[k];
                if (dp[j-1][k]<minn) minn=dp[j-1][k];
            }
            dp[j][j]=minn+a[j]*p[j]+10*p[j];
        }
        minn=2100000000;
        for (int j=0;j<n;++j)
            if (dp[n-1][j]<minn) minn=dp[n-1][j];
        printf("%d\n",minn);
    }
    return 0;
}