NYOJ Cut the rope

本文主要是介绍NYOJ Cut the rope，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

 

We have a rope whose length is L. We will cut the rope into two or more parts, the length of each part must be an integer, and no two parts have the same length.
　　Your task is to calculate there exists how many results after the cutting. We say two results are different if and only if there is at least one part, which we can find in one result but can not find in the other result

输入

There is an integer T (1 <= T <= 50000) in the first line, which indicates there are T test cases in total.
　　For each test case, there is only one integer L (1 <= L <= 50000) which has the same meaning as above.

输出

For each test case, you should output the correct answer of the above task in one line.
　　Because the answer may be very large, you should just output the remainder of it divided by 1000000 instead

样例输入

3
2
3
6

样例输出

0
1
3

上传者

 

动态规划，dp[i][j]表示i分解陈j个数的数量,

dp[i][j]=dp[i-j][j]（不包含1）+dp[i-j][j-1]（包含1）;

 

AC代码：

 

 

# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
using namespace std;
const int mod=1000000;
int dp[50010][320];
int main(){int n, t, i, j, k, sum;memset(dp, 0, sizeof(dp));dp[3][2]=1;dp[4][2]=1;dp[5][2]=2;dp[6][2]=2;dp[6][3]=1;for(i=1; i<=50000; i++){dp[i][1]=1;}for(i=7; i<=50000; i++){for(j=2; j*(j+1)/2<=i; j++){dp[i][j]=(dp[i-j][j]+dp[i-j][j-1])%mod;}}scanf("%d", &t);for(i=1; i<=t; i++){scanf("%d", &n);sum=0;for(k=2; k*(k+1)/2<=n; k++){sum=(sum+dp[n][k])%mod;}printf("%d\n", sum);}return 0;
}

 

 

这篇关于NYOJ Cut the rope的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---