专栏文章

题解：B3803 [NICA #1] 上大分

kkoukou
B3803题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqkk1r4
此快照首次捕获于
2025/12/04 06:19
3 个月前
此快照最后确认于
2025/12/04 06:19
3 个月前
查看原文
最近刚学dp，来写一篇题解。
我们不妨定义 dpi,jdp_i,_j 为到了第 ii 场比赛，参加了 jj 场时的最高分数。
若不参加这场比赛，则 dpi,jdp_i,_j 为 dpi−1,jdp_{i-1},_j。
若参加这场比赛，则 dpi,jdp_i,_j 为 dpi−1,j−1+⌊ai−dpi−1,j−14⌋dp_{i-1},_{j-1}+\lfloor\frac{a_i-dp_{i-1},_{j-1}}{4}\rfloor，但是这里有 division 2，所以需判断 dpi−1,j−1dp_{i-1},_{j-1} 是否小于 19001900。
再讲初始化，dp0,0=xdp_0,_0=x。
最后是答案，及在 dpn,0dp_n,_0 到 dpn,kdp_n,_k 之间去最大值即可。

code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 1;
int n, k, x, ans = -1e9, dp[N][N];
struct node
{
	int x, c;
}s[N];
int main()
{
	cin >> n >> k >> x;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i].x >> s[i].c;
	}
	dp[0][0] = x;//初始化
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= min(i, k); j++)
		{
			if(j == 0)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else if(s[i].x == 1 || s[i].x == 2 && dp[i - 1][j - 1] < 1900)
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (int)floor((s[i].c - dp[i - 1][j - 1]) / 4.0));
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}//状态转移
		}
	}
	for(int i = 0; i <= k; i++)
	{
		ans = max(ans, dp[n][i]);
	}//答案
	cout << ans;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...