洛谷P1336 最佳课题选择 题解

Edited on | In | Comments:

Problem

题目描述

Matrix67要在下个月交给老师$n$篇论文，论文的内容可以从$m$个课题中选择。由于课题数有限，Matrix67不得不重复选择一些课题。完成不同课题的论文所花的时间不同。具体地说，对于某个课题$i$，若Matrix67计划一共写$x$篇论文，则完成该课题的论文总共需要花费$A_i×x^{B_i}$个单位时间（系数$A_i$和指数$B_i$均为正整数）。给定与每一个课题相对应的$A_i$和$B_i$的值，请帮助Matrix67计算出如何选择论文的课题使得他可以花费最少的时间完成这$n$篇论文。

输入输出格式

输入格式：

第一行有两个用空格隔开的正整数$n$和$m$，分别代表需要完成的论文数和可供选择的课题数。

以下$m$行每行有两个用空格隔开的正整数。其中，第$i$行的两个数分别代表与第$i$个课题相对应的时间系数$A_i$和指数$B_i$。

输出格式：

输出完成$n$篇论文所需要耗费的最少时间。

输入输出样例

1
2
3
4
5
Input #1
10 3
2 1
1 2
2 1
1
2
Output #1
19

样例说明：
4篇论文选择课题一，5篇论文选择课题三，剩下一篇论文选择课题二，总耗时为$2×4^1+1×1^2+2×5^1=8+1+10=19$。可以证明，不存在更优的方案使耗时小于$19$。

Solution

很简单的一道dp题。

虽然它长得像完全背包，但实质上是01背包。指数运算使得相同课题的耗时不能叠加，只能写3重循环来处理。这里背包中所有物品的大小都是1。

这道题求的是最小值，怎么办呢？将dp数组赋一个极大值，dp[0]=0，之后dp做的是min()而不是max()。

状态转移方程：

1
2
//j是目前背包大小，k是写作篇数，cost是耗时
f[j] = min(f[j], f[j - k] + cost);

另外，答案较大，需要开long long。

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200 + 5;
const int MAXM = 20 + 5;
int n, m;
int a[MAXM], b[MAXM];
long long f[MAXN];

long long Pow(int x, int y) //卡速米
{
    long long ret = 1, f = x;
    while(y > 0)
    {
        if(y & 1) ret *= f;
        y >>= 1;
        f *= f;
    }
    return ret;
}

int main()
{
    for (int i = 1; i < MAXN; i++) f[i] = 0x7fffffffff;  //赋极大值
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= m; i++)
        for (int j = n; j >= 1; j--)
            for (int k = 1; k <= j; k++)
            {
                long long cost = a[i] * Pow(k, b[i]);   //计算花费
                f[j] = min(f[j], f[j - k] + cost);
            }
    cout << f[n] << endl;
    return 0;
}

Data

评测请至洛谷P1336。