HDU_1028_Ignatius and the Princess III_(母函数,dp)
2024-10-21 18:59:50
Ignatius and the Princess III
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 17917 Accepted Submission(s): 12558
Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
4
10
20
10
20
Sample Output
5
42
627
42
627
看了题解,学了两种方法。一种是母函数,一种是dp。
母函数:组合数学方法,第一次接触。
此题构造的母函数(1+x^1+x^2+x^3...+x^n)(1+x^2+x^4+x^6...+x^2n).....
第一项表示(0个1,1个1,2个1,3个1...),第二项表示(0个2,1个2,2个2,3个2,4个2...)以此类推。
展开后,每一项的指数表示划分的这个数,系数表示该数的划分数。
import java.util.*;
import java.io.*; public class Main { public static int cal(int n)
{
int c1[]=new int [n+1];
int c2[]=new int [n+1];
for(int i=0;i<=n;i++)
{
c1[i]=1;
c2[i]=0;
}
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n;j++)
for(int k=0;k+j<=n;k+=i)
c2[j+k]+=c1[j];
for(int j=0;j<=n;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
return c1[n];
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n;
while(in.hasNext())
{
n=in.nextInt();
System.out.println(cal(n));
}
} }
dp:
dp[i][j]表示i这个数划分为最大加数不超过j的划分数。
if(i>j) dp[i][j]=dp[i][j-1]+dp[i-j][j];
else if(i==j) dp[i][j]=dp[i][j-1]+1;
else if(i<j) dp[i][j]=dp[i][i];
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std; int dp[][]; int main()
{
int n,m;
//dp[1][1]=1;
for(int i=; i<=; i++)
for(int j=; j<=; j++)
{
if(j==)
dp[i][j]=;
else if(i==j)
dp[i][j]=dp[i][j-]+;
else if(i>j)
dp[i][j]=dp[i][j-]+dp[i-j][j];
else if(i<j)
dp[i][j]=dp[i][i];
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n][n]);
} return ;
}
最新文章
- Java基础-一个java文件多个类的问题
- Python的平凡之路(17)
- piap.windows io 监测attilax总结
- 更改vs自带的模板
- MVC(二)
- Java和C++中的static
- javascript中数组揭秘
- Angularjs 中使用指令绑定点击事件
- <;汇编语言系列>;计算机硬件系统与汇编
- 配置linux平台下基于vim的开发环境
- C51指针类型和存储区的关系详解
- unity3d ngui-TweenRotation-TweenPosition-TweenScale
- x86/x64/x86_64/i386/ia32/ia64/amd/amd64 辨析
- glance系列一:glance基础
- HTML5 &; auto download image
- JDK1.7新特性,语言篇
- JS弹出div简单样式
- Spring 计划 7.0
- http协议缓存小结
- ubuntu18.10手动安装mysql5.5
热门文章
- - >; 贪心基础入门讲解五——任务执行顺序
- PHP与WCF第一次亲密接触
- [转]SQL Server编程:SMO介绍
- vijos- P1383盗窃-黑珍珠 (python + 代码优化)
- windows下检測文件改变
- 如何让图片开口说话 3DMeNow教程
- Python图像处理库:PIL中Image,ImageDraw等基本模块介绍
- iOS UITextView 高度随文字自己主动添加,并尾随键盘移动(二)
- Android自定义用户控件简单范例(二)
- 【Spark】Stage生成和Stage源代码浅析