问题标题: 估分！

首先发几句：

 

4次里面3次一等1次二等

难道连老天也在祝福我吗

 

我写的市赛第四题是子集记忆化

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],b[1000005],f[1000005];
long long dfs(long long idx){
	if(f[idx]!=0)
		return f[idx];
	if(idx>n)
		return 0;
	return f[idx]=max(dfs(idx+1),dfs(idx+b[idx]+1)+a[idx]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	cout<<dfs(1);
	return 0;
}

 

汪宇航在2023-03-19 20:44:21追加了内容

引用自创诗：

1.
暴力出奇迹，骗分过阳历。
记忆扫O(k)，爆搜不卡常。
小模拟，仍辣**。算CS，穷举废。
2.
递推会被 T，爆搜有卡常。
输出有精度，四舍没五入。
穷举会  CE，贪心医假病。
模拟不  AC，代码漫天飞。

 

引入正题：

发表一下个人对市赛题目的见解。

第一题：

对应

输出有精度，四舍没五入。

没什么难点，本人为了方便开了一个const去缩2*3.14：

然后printf时需注意四舍五入：

然后：

第二题：

对应

穷举会  CE，贪心医假病。

桶之后应该是从1000~1倒叙遍历，采用贪心式的循环最大值：

然后：

第三题：

对应

模拟不  AC，代码漫天飞。

看到测试数据时，应该想到的就是暴力好吧

但是有个问题那就是我们在写暴力的时候代码的顺序会有错的可能所以需要注意注意再注意

最理想的情况当然是一个没错了额

自然：

压轴题：第四题

对应

递推会被 T，爆搜有卡常。

与

记忆扫O(k)，爆搜不卡常。

大部分人写的是动态规划，不过我直接子集记忆化把O(kN)里的常数项k缩成1了，而且写起来很简单：

 

不过我在这里把dfs的两个if写反了，这样的话可能会RE，不过酷町编程的数据有点弱所以依然满分，不过市赛就不一定了。

 

个人认为可以考到370~400了（如果不出别的幺蛾子的话）

难度3⭐（满分5⭐的话）