首页 > 代码库 > NYOJ 645 骰子

NYOJ 645 骰子

骰子

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

 

小明有m个骰子,每一个骰子都是标准六面骰子,问题很简单,请求出他掷出固定点数的方法数

输入
有多组测试数据
每行一个整数m,k,m表示骰子的数量,k表示要掷的点数(1<=m<=100, 0<= k < 1000)
输出
每行输出掷出固定点数的方法数,算出的结果对100007取余
样例输入
2 1

2 3
样例输出
0

2
好坑爹啊!居然WA了这么多次!时间和内存耗费也很大!奋斗
AC码:
#include<stdio.h>
#include<string.h>
int dp[1001][1001];
void DP()
{
	memset(dp,0,sizeof(dp));
	dp[1][1]=1; dp[1][2]=1; dp[1][3]=1;
	dp[1][4]=1; dp[1][5]=1; dp[1][6]=1;
	int i,j,k,t;
	for(i=2;i<=1000;i++)
	{
		for(j=i;j<=6*i&&j<=1000;j++)
		{
			k=j;
			t=j-6;
			while(k>=i&&k>t)
			{
				dp[i][j]=(dp[i][j]+dp[i-1][k-1])%100007;
				k--;
			}
		}
	}
}
int main()
{
	int n,k;
	DP();
	while(~scanf("%d%d",&n,&k))
	{
		printf("%d\n",dp[n][k]);
	}
	return 0;
}