hnust_yangyanjun

分类

大数加法(1) 尺取法(1) 面经(4) 题解(119)

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共24篇）

[SCOI2008]着色方案

题意：给你n种染料，每种染料可以使用Ci次，同一种染料不能连续使用，求用完所有染料的方案数为多少种？思路：纯动态规划，我们用dp[a][b][c][d][e][last]描述一个还可以使用一次的染料为a种，还可以使用两次的染料为b种，.....,可以使用五次的染料为f种时上一次染色为使用还可以使用...

dp

2020-07-26

1 521

[SCOI2007]压缩

题意：给与一个长度不超过50的字符串，它可以按下列方式压缩：M是开始，R是重复从前一个M开始的字符串。求字符串压缩后的最短长度。思路：区间dp:dp[i][j][0/1]:dp[i][j][0]表示从i到j这段字符串中没有有M、dp[i][j][1]表示从i到j这段字符串中可以出现M的最少字符数。...

dp

2020-07-21

1 674

kingdom

题意：有一棵节点数为n的树，每一个子节点向父节点传送消息时，如果以父节点为根的子树中该节点为根的子树中节点数最多，则该节点花费为父节点的花费，否则为父节点花费+1.求所有节点一层一层向根节点传送消息的花费之和尽量大时的花费为多少？思路：这题我们可以用dp解决，我们求的是n个节点树的最大花费...

dp

2020-07-19

1 567

矩阵取数游戏

题意：给出一个n*m的矩阵，每一次取数从每一行中取一个数，每行取数的得分为每行所取数a[i][j] * ,k表示第几次取，且每次取数只能取头或者尾。求取完后的得分最大值？思路：我们可以发现每一行的取数只与当前行有关，所以该题相当于求n次数组中取数得分之和。我们可以区间dp解决。每一次不断增加区间...

__int128 dp

2020-07-14

1 994

[SCOI2005]最大子矩阵

题意：在一个n*m的矩阵中选择k个子矩阵，这k个子矩阵互不相交，求这k个子矩阵分值最大为多少？思路：dpdp[k][i][j]为在第一列前i个，第二列前j个，选择k个矩阵的最大值。分析我们动态所加的一个元素参与结果的情况。既枚举所加元素在第一列前i个，第二列前j个中所有矩阵加上在该矩阵外选（k-1...

dp

2020-06-12

0 543

德马西亚万岁

题意：有一个n*m的地图，为0不可以站人，为1可以站人，二个人不能相邻，求合理的方案数？思路：状压dpdp[i][j]为第i行状态为j的方案数（状态为第i行二进制转化为十进制的值，既一个二进制为该行的整数）。d[i]表示地图中第i行这m位取反表示的十进制。如果该状态合法，则j&(j-1)=...

dp

2020-06-09

0 527

管道取珠

题意：链接：https://ac.nowcoder.com/acm/problem/17621来源：牛客网管道取珠是小X很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图1所示：游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。...

dp

2020-06-03

1 674

货币系统

题意：有n种货币，每一种货币面值为a[i]，并且每种货币有无穷个，请问只需多少种货币可以达到和这n种货币一样的支付范围？思路：多重dp，将a数组按升序排列，如果第i种货币的值可以被前i-1种货币组成，则该面值的货币可以不要，计算不能被组成的货币种类数即可。代码： #include<bits...

dp

2020-05-27

0 727

比赛

题意：一场比赛总共有12个题，对于第i个题，有a[i]的几率解决它，如果不能解决，则你有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法，请问最终你们队伍解出0-12题的概率分别是多少？思路：每一题单独的解决概率的d[i]=a[i]+(1-a[i])...

dp

2020-05-21

0 466

加分二叉树

题意：给出一个n个节点的二叉树，中序遍历为1，2，3,......，n;每个节点都有一个分数（均为正整数），任一棵子树subtree的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数求二叉树的最大分数和前序遍历？思路：f[i][j]为从第i个...

dp

2020-05-18

0 563