dilingtian

分类

题解(18)

/ 注册

全部文章（共4篇）

题解 | #[NOIP2007]守望者的逃离#

dpdpdp做法，先全用魔法更新一遍动态数组，然后再加入常规走法更新 AC代码 #include <bits/stdc++.h> using namespace std; const int N = 1e6; int dp[N]; int main(void) { int m, s, ...

动态规划贪心

2022-11-29

1 379

题解 | #被3整除的子序列#

如果一个数可以被333整除，那么这个数的每一位之和一定是333的倍数证明:题解 | 3的倍数定义：数组dp[i][j]dp[i][j]dp[i][j]表示以iii为结尾组成的子序列，数位之和对333取余为jjj的方案数动态转换方程： num=(s[i]−′0′)%3num=(s[i]-'0')...

动态规划

2022-11-28

1 423

题解 | #小A买彩票#

这是一个计算概率的问题，最直接的做法是将满足条件的情况数算出，除以所有情况。观察到本题的数据nnn只有30，所以所有情况最多只有4304^{30}430种，即260<2642^{60}<2^{64}260<264。方法一：时间复杂度（N5N^5N5）题意中说只有四种牌，我们进行...

动态规划暴力

2022-11-04

1 471

题解 | #乌龟棋#

本题不可以采用dfs爆搜，极其容易TLE，因为时间复杂度大致为:4M4^M4M,而M的大小为120，即使在运算过程中达不到4M4^M4M，但是也远远大于10710^7107，所以我们应该使用动态规划。题目中说只有四种牌，这个是可以利用的条件。我们dp的状态表示每张牌已经使用了多少张，我们根据使用的牌...

动态规划

2022-11-03

1 381