【动态规划】数的划分
时间限制: 1 Sec 内存限制: 256 MB
提交: 9 解决: 7
[提交][状态][讨论版]
题目描述
积
极探索太空的回报是丰厚的，因为魔法世界的科学家后来通过挖掘史前文明遗址发现，他们所在的星球，每隔一亿五千万年左右就会发生一次由天外陨石或其他意外
事件引发的物种大灭绝。称霸星球一亿多年的恐龙，就是因此而灭绝的。只有积极进取，锐意创新的宇宙文明，才有可能躲过这场“天罚”。现在，天顶星人对魔法
世界发动了大规模陨石攻击，魔法世界的太空防御系统及时作出反应，将防御能量n分成k份以对付k个陨石，已知每份不能为空（否则会被陨石击中），任意两份
不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的：1，1，5； 1，5，1； 5，1，1。问有多少种不同的分法。
输入
n，k (6<n≤200，2≤k≤6)
输出
一个整数，即不同的分法。
样例输入
7 3
样例输出
4
【分析】
.将n划分成k个数的划分法：
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
方法可以分为两类：
第一类: n 份中不包含 1 的分法，为保证每份都 >= 2，可以先拿出 k 个 1 分
到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
第二类: n 份中至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩
下的 n- 1 再分成 k- 1 份即可，分法有：dp[n-1][k-1]
详细解读见http://blog.csdn.net/athenaer/article/details/8265234
#include <iostream> #include <cstring> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <time.h> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #define inf 0x3f3f3f3f #define mod 1000000007 typedef long long ll; using namespace std; const int N=310; int v[N],w[N]; int dp[N][N]; void init() { for(int i=0;i<=200;i++) dp[0][i]=0; for(int i=1;i<=200;i++) { for(int j=1;j<=6;j++) { if(i<j)dp[i][j]=0; else if(i==j)dp[i][j]=1; else dp[i][j]=dp[i-j][j]+dp[i-1][j-1]; } } } int main() { int t,n,m,f; init(); cin>>n>>m; cout<<dp[n][m]<<endl; return 0; }