概述
-
-
- 2018 牛客多校第二场 个人总结+部分题解
-
- 1 dp 入门题
- B discount
- C message
- D money
- E tree
- F trade
- G transform
- H travel
- I car
- J farm
- K carpet
-
- 2018 牛客多校第二场 个人总结+部分题解
-
2018 牛客多校第二场 个人总结+部分题解
1 dp 入门题
dp[j][i] 表示 到i这个点是跑过来还是走过来的，走过来就是1，跑过来就是0
转移方程
上一次是跑过来或者走过来，这一次都可以走
dp[0][i+1]+=(dp[0][i]+dp[1][i])
d
p
[
0
]
[
i
+
1
]
+
=
(
d
p
[
0
]
[
i
]
+
d
p
[
1
]
[
i
]
)
如果本次是走过来的，则下次可以跑
dp[1][i+k]+=dp[0][i]
d
p
[
1
]
[
i
+
k
]
+
=
d
p
[
0
]
[
i
]
void init(void){
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 0;i < maxn; ++i){
dp[0][i+1] += (dp[0][i]+dp[1][i]);
dp[0][i+1] %= mod;
dp[1][i+k] += dp[0][i];
dp[1][i+k] %= mod;
}
for(int i = 1;i < maxn; ++i)
ans[i] =(ans[i-1]+dp[0][i]+dp[1][i])%mod;
}
B discount
dp+基环内向树
具体做法看题解（先挖坑）
C message
凸包+dp
D money
就是一个求连续不下降区间的过程，模拟一下就行了
E tree
逆向dp
F trade
先排除被干扰的，就跟几何没关系了。。
G transform
看这里详细题解
H travel
裸的树形dp
I car
本来以为是个高科技，没想到推出来试了一发是个模拟
J farm
这一题有很多操作需要学啊
学弟博客
K carpet
最后
以上就是安静白猫为你收集整理的2018 牛客多校第二场的全部内容，希望文章能够帮你解决2018 牛客多校第二场所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复