NYOJ--743

向右看齐 2022-09-18 00:52 17阅读 0赞

拿到这个题找规律找了好久...画了半天才发现规律...结果网上一搜..就是C(M,N)的求取啊..坑啊..

先说简单的思路..循环的递增其实就是从一个长度为n的递增序列,然后每个数都不一样,从中找出m个数..所以直接就是C(M,N)...

而且用C(M,N)公式计算的话还是复杂了.可以直接用C(M,N)=C(M,N-1)+C(M-1,N-1)来算出一张表来..每次输入直接在表中查找即可..当然这是别人的思路..

我还是说下我找的规律吧..

一开始看半天,也写不出公式..于是选择按照<怎样解题>的思路来..先自己从简单的情况慢慢找...尽信书不如无书啊...

1.当m==1的时候,很显然次数为n

2.当m==2的时候,算出每次第一层循环变化时候第二层循环中执行的次数,可以看出是从n-1一直累加到1.

3.当m>=3的时候计算的情况就变了.就从一维的变为多维的了.为了方便说,就以m==3来说.每排都是由最下面两层循环计算的,然后再多一层,那么就会多一排出来.所以可以看做是二维的.同理,当m==4的时候,最下面三排构成一个二维的..然后最上面排构成第三个维度..这就是递归的神奇之处吧!下一个维度由多个上一维度组成.于是就可以看成是一个动态规划的问题了..

貌似说的有些复杂..还是贴出别人思路的代码吧..自己写的..虽然差不多...

#include<stdio.h>
    #include<string.h>
    
    int map[2001][2001]; 
    
    
    int main()
    {
    	int i,j;
    	int n,m;
    	int fenzi,fenmu;
    
    	for(i=1;i<=2000;i++)
    	{
    		for(j=i;j<=2000;j++)
    		{
    			if(i==1)
    			{
    				map[i][j]=j%1009;
    			}
    			else if(i==j)
    			{
    				map[i][j]=1;
    			}
    			else
    			{
    				map[i][j]=map[i][j-1]+map[i-1][j-1];
    				map[i][j]%=1009;
    			}
    		}
    	}
    
    	while(scanf("%d %d",&m,&n))
    	{	
    		if(m+n==0)
    			break;
    		printf("%d\n",map[m][n]);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - 743 网络延迟时间

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [743. 网络延迟时间 - 力扣（Leet

绝地灬酷狼/ 2023年09月23日 13:43/ 0 赞/ 71 阅读

相关 NYOJ--743

　拿到这个题找规律找了好久...画了半天才发现规律...结果网上一搜..就是C(M,N)的求取啊..坑啊.. 　先说简单的思路..循环的递增其实就是从一个长度为n的递增序列,

向右看齐/ 2022年09月18日 00:52/ 0 赞/ 18 阅读

相关 743_lshort中文版书籍获取

全部学习汇总： [https://github.com/GreyZhang/g\_Tex][https_github.com_GreyZhang_g_Tex]

Bertha 。/ 2022年09月07日 15:56/ 0 赞/ 110 阅读

相关 Leetcode743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times\[i\] = (ui, vi, wi)，其中 ui 是源节

冷不防/ 2022年09月02日 11:55/ 0 赞/ 112 阅读

相关 743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times\[i\] = (ui, vi, wi)，其中 ui 是源节

旧城等待，/ 2022年09月02日 11:40/ 0 赞/ 145 阅读

相关 Leetcode 743. 网络延迟时间

题目重述有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过有向边的传递时间。 times\[i\] = (ui, vi, wi)，其

末蓝、/ 2022年09月02日 11:36/ 0 赞/ 113 阅读

相关 NYOJ 308

Substring 时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述 You are given a string input.

客官°小女子只卖身不卖艺/ 2022年06月17日 13:20/ 0 赞/ 131 阅读

相关 NYOJ 248

BUYING FEED 时间限制： 3000 ms | 内存限制： 65535 KB 难度： 4 描述 Farmer John needs to travel

清疚/ 2022年06月17日 10:28/ 0 赞/ 124 阅读

相关 NYOJ 168

房间安排时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述 2010年上海世界博览会(Expo2010),是第41届世界博览会。于

冷不防/ 2022年06月17日 05:53/ 0 赞/ 129 阅读

相关 NYOJ 541

最强DE 战斗力时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述春秋战国时期，赵国地大物博，资源非常丰富，人民安居乐业。但许多

Myth丶恋晨/ 2022年06月16日 03:48/ 0 赞/ 140 阅读