Atcoder Beginner Contest 104C - All Green 解题报告

Atcoder Beginner Contest 104C - All Green 解题报告

1 题目链接

传送门

2 题目大意

题目：绿色全开

题目大意：

在 $Atcoder$ 网站上，题目有 $D$ 种分值，分别是 $100$，$200$，…$100D$，分值为 $100i$ 的题目有 p i p_i pi​ 道，如果你把分值为 $100i$ 的题目全部做完，可以获得额外的 c i c_i ci​ 分，高桥小朋友想要得到 $G$ 分，问他至少要做多少道题。题目保证有解。

3 解法分析

二进制枚举非常好想，代码也十分简单。

从贪心的角度考虑：

如果没有 c i c_i ci​，那就直接从分最高的题目开始做。二进制枚举要做哪几种题，从 $pi$ 大的开始做，计算要做多少题，统计答案即可。

复杂度： O ( 2 n ) O(2^n) O(2n)

这种方法也可以用 $dfs$ 的方法实现。

$dfs$：

考虑到这道题的 $D$ 相对较小， O ( 2 n ) O(2^n) O(2n) 的 $dfs$ 显然也是可以过的。

用 v i s i vis_i visi​ 记录分值为 $i$ 的题是否做完，用 $dfs$ 搜索 $vis$，$cal$ 函数补充计算即可。

$dp$ 显然也能达到类似的效果。

首先考虑二维 $dp$：

d p i , j dp_{i,j} dpi,j​ 表示在前 $i$ 套题目中，做了 $j$ 道所能获得的最大分值。

转移方程分为一下两种情况：

1. 第一种是没有做完第 $i$ 套的题目，此时转移方程：

   d p i , j + k = max ⁡ { d p i , j + k , d p i − 1 , k + j × i × 100 } dp_{i,j+k} = \max\{dp_{i,j+k}, dp_{i-1,k} + j\times i\times 100\} dpi,j+k​=max{dpi,j+k​,dpi−1,k​+j×i×100}

2. 第二种是做完了第 $i$ 套的题目，此时转移方程：

   d p i , j + k = max ⁡ { d p i , j + k , d p i − 1 , k + j × i × 100 + c i } dp_{i,j+k} = \max\{dp_{i,j+k}, dp_{i-1,k} + j\times i\times100 + c_i\} dpi,j+k​=max{dpi,j+k​,dpi−1,k​+j×i×100+ci​}

显然这就已经可以过了。

再考虑一维：

d p i dp_i dpi​ 表示做了 $i$ 道题可以得到的最多分数。

转移式还是分成两种情况：

1. 若 j = p i j=p_i j=pi​，转移式为：

   d p i = max ⁡ { d p i − j + i × p i × 100 + c i } dp_i=\max\{dp_{i-j}+i\times p_i\times100+c_i\} dpi​=max{dpi−j​+i×pi​×100+ci​}

2. 否则，转移式为

   d p i = max ⁡ { d p i − j + i × j × 100 } dp_i=\max\{dp_{i-j}+i\times j\times100\} dpi​=max{dpi−j​+i×j×100}

最后枚举一下答案即可。

4 解法总结

• 二进制枚举
• $dfs$
• 二维dp
• 一维dp

5 AC Code

5.1 二进制枚举

#include 
#define inf 0x3f3f3f3f
#define N 17
using namespace std;int d, g;
int p[N], c[N];int main() {scanf("%d%d", &d, &g);int maxn = (1 << d) - 1, ans = inf;for (int i = 1; i <= d; ++i)scanf("%d%d", &p[i], &c[i]);for (int i = 0; i <= maxn; ++i) {int cnt = 0, res = g;for (int j = d; j >= 1 && res > 0; --j)if (i & (1 << (j - 1))) {int tmp = p[j] * j * 100;if (tmp >= res) {cnt += (res + 100 * j - 1) / (100 * j);res = 0;break;}else {res -= tmp + c[j];cnt += p[j];}}if (res <= 0)ans = min(ans, cnt);}printf("%d\n", ans);return 0;
}

5.2 $dfs$

#include 
#define N 17
using namespace std;int d, g;
int p[N];
int c[N];
bool vis[N];
int ans = 1e9;int cal(int s) {for (int i = d; i >= 1; --i)if (!vis[i]) {if (g - s >= p[i] * i * 100)return 1e9;elsereturn ceil((g - s) / (i * 100.0));}return 1e9;
}void dfs(int t, int s, int n) {if (s >= g) {ans = min(ans, n);return;}ans = min(ans, n + cal(s));if (t > d)return;vis[t] = 0;dfs(t + 1, s, n);vis[t] = 1;dfs(t + 1, s + p[t] * 100 * t + c[t], n + p[t]);
}int main() {scanf("%d%d", &d, &g);for (int i = 1; i <= d; ++i)scanf("%d%d", &p[i], &c[i]);dfs(1, 0, 0);printf("%d\n", ans);return 0;
}

5.3 二维dp

#include 
using namespace std;int d, g;
int c[27];
int ans, p[27];
int dp[27][1007];int main() {scanf("%d%d", &d, &g);for (int i = 1; i <= d; ++i) {scanf("%d%d", &p[i], &c[i]);ans += p[i];}for (int i = 1; i <= d; ++i)for (int j = 0; j <= p[i]; ++j)for (int k = 0; k <= ans - j; ++k)if (j != p[i])dp[i][j + k] = max(dp[i][j + k], dp[i - 1][k] + j * i * 100);elsedp[i][j + k] = max(dp[i][j + k], dp[i - 1][k] + j * i * 100 + c[i]);for (int i = 0; i <= ans; ++i)if (dp[d][i] >= g)return printf("%d\n", i), 0;return 0;
}

5.4一维dp

#include 
#define N 1007
using namespace std;int n, g;
int f[N], a[N], b[N];int main() {scanf("%d%d", &n, &g);for (int i = 1; i <= n; ++i)scanf("%d %d", &a[i], &b[i]);for (int i = 1; i <= n; ++i) for (int j = 1000; j >= 0; --j) for (int k = min(j, a[i]); k >= 0; --k) f[j] = max(f[j], f[j - k] + k * i * 100 + ((k == a[i]) ? b[i] : 0));for (int i = 0; i <= 1000; ++i)if (f[i] >= g)return printf("%d\n", i), 0;return 0;
}

完结撒花。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！