小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。 比如 ___+12=34 ,那么横线填的一定是22 现在,这个游戏到了最后一关,这一关的等式很奇特:_+_+_+…+_=n 这里可以填任意多个正整数(甚至可能是 1个),只要这些数的和等于n 即可。 但是,有一个额外的限制,填入的所有数必须小于等于 k,大于等于1 ,填入的数的最大值必须大于等于d 。   请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案 mod(998244353)后输出。-笔试面试资料

这是qklbishe.com第7167 篇笔试面试资料
提供答案分析,通过本文《小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。 比如 ___+12=34 ,那么横线填的一定是22 现在,这个游戏到了最后一关,这一关的等式很奇特:_+_+_+…+_=n 这里可以填任意多个正整数(甚至可能是 1个),只要这些数的和等于n 即可。 但是,有一个额外的限制,填入的所有数必须小于等于 k,大于等于1 ,填入的数的最大值必须大于等于d 。   请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案 mod(998244353)后输出。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。

比如 ___+12=34,那么横线填的一定是22

现在,这个游戏到了最后一关,这一关的等式很奇特:_+_+_+…+_=n

这里可以填任意多个正整数(甚至可能是1个),只要这些数的和等于n即可。

但是,有一个额外的限制,填入的所有数必须小于等于k,大于等于1,填入的数的最大值必须大于等于d

 

请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案mod(998244353)后输出。

小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。       比如 ___+12=34 ,那么横线填的一定是22       现在,这个游戏到了最后一关,这一关的等式很奇特:_+_+_+...+_=n        这里可以填任意多个正整数(甚至可能是  1个),只要这些数的和等于n  即可。       但是,有一个额外的限制,填入的所有数必须小于等于  k,大于等于1  ,填入的数的最大值必须大于等于d  。              请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案  mod(998244353)后输出。 零葬
动态规划求解,构建一个(n+1)*2dp数组,dp[i][0]表示凑出i时没有使用大于等于d的数的方案数,dp[i][1]表示凑出 时用了大于等于d的数的方案数。在凑某个数i时,状态转移有如下情况:
(1) 如果此时要填的数 j<d
因为凑成 没有使用大于等于 的数,那凑成 i-j 也没有使用大于等于 的数,dp[i][0]只会从dp[i-j][0]转移过来dp[i][1]只会从dp[i-j][1]转移过来。而这种填数游戏在 i-j 的填数方案已经确定的情况下,现在要填数 应该满足累加的原则,所以在遍历 时,每取一个值就把前面的方案数加一次,状态转移方程为:
                                                   dp[i][0] dp[i][0] + dp[i-j][0]
                                                   dp[i][1] dp[i][1] + dp[i-j][1]
(2) 如果此时要填的数 j>=d:因为现在要填的 已经满足大于等于 了,所以填数方案中至少得有一个数大于等于d的成就已经达成,凑成 i-j 有没有使用大于等于 的数已经不重要。此时只更新dp[i][1]dp[i][1]可以从dp[i-j][0]dp[i-j][1]两个状态转移过来,状态转移方程为:
                                                   dp[i][1] dp[i][1] + ∑(dp[i-j][0]+dp[i-j][1])
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException;  public class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String[] params = br.readLine().trim().split(" ");         int n = Integer.parseInt(params[0]);         int k = Integer.parseInt(params[1]);         int d = Integer.parseInt(params[2]);         // dp[i][0]表示凑成i时没有用大于等于d的方案数,dp[i][1]表示凑成i时用了大于等于d的方案数         long[][] dp = new long[n + 1][2];         dp[0][0] = 1;         for(int i = 1; i <= n; i++){             // 题目要求填的正整数范围是从1~k,但是也不能超过目标值i             for(int j = 1; j <= Math.min(k, i); j++){                 if(j < d){                     dp[i][0] = (dp[i][0] + dp[i - j][0]) % 998244353;                     dp[i][1] = (dp[i][1] + dp[i - j][1]) % 998244353;                 }else                     dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % 998244353;             }         }         // 输出凑出了n并且使用了大于等于d的数的方案数         System.out.println(dp[n][1]);     } }

今天 11:38:45 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小团和小美正在玩一个填数游戏,这个游戏是给一个等式,其中有一些数被挖掉了,你需要向其中填数字,使得等式成立。 比如 ___+12=34 ,那么横线填的一定是22 现在,这个游戏到了最后一关,这一关的等式很奇特:_+_+_+…+_=n 这里可以填任意多个正整数(甚至可能是 1个),只要这些数的和等于n 即可。 但是,有一个额外的限制,填入的所有数必须小于等于 k,大于等于1 ,填入的数的最大值必须大于等于d 。   请你计算,有多少个不同的等式满足这些限制。由于答案可能很大,请将答案 mod(998244353)后输出。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情