AtCoder Beginner Contest 192 F.Potion

题目链接

Problem Statement

There are N kinds of materials. Material i has a magic power of Ai.

Takahashi, the magician, wants to make a potion by choosing one or more kinds from these materials and mixing them.

At the moment when he makes a potion by mixing k kinds of materials, the magic power of the potion is the sum of the materials used. Then, every second, its magic power increases by k. Note that the increase of the magic power is a discrete - not continuous - process.

Takahashi will mix materials just once, at time 0. What is the earliest time he can get a potion with a magic power of exactly X?

Under the constraints, it can be proved that it is possible to make a potion with a magic power of exactly X.

Sample Input 1

3 9999999999
3 6 8

Sample Output 1

4999999994

Sample Input 2

1 1000000000000000000
1

Sample Output 2

999999999999999999

动态规划，背包DP~

首先我们可以暴力选取材料的种类 $c$，$c\in[1,n]$，用 dp[i][j][k] 表示前 i 个数里选 j 个数且模数为 k 的最大值 sum，且 k=sum%c，则有如下的状态转移方程：

$$dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][(k - a[i] \% t + t) \% t] + a[i])$$

计算出最大值后对应 c 种材料所需时间即为 $t=\frac{x-dp[n][c][x\%c]}{c}$，AC 代码如下：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, x, ans = INT64_MAX, a[105], dp[105][105][105];

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int t = 1; t <= n; t++) {
        memset(dp, 0x80, sizeof(dp));
        dp[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= t; j++) {
                for (int k = 0; k < t; k++) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][(k - a[i] % t + t) % t] + a[i]);
                }
            }
        }
        if (dp[n][t][x % t] > 0) ans = min(ans, (x - dp[n][t][x % t]) / t);
    }
    cout << ans;
    return 0;
}