置苹果

放苹果

总时间限制:
    1000ms
内存限制:
    65536kB

描述
    把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入
    第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
    对输入的每组数据M和N，用一行输出相应的K。
样例输入

    1
    7 3

样例输出

    8
我给的答案，但是提示错误，求解答，

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

   static  int sum;
int count1(double M,double N)
{//int sum=0;
if(N==1)
{sum=1;
return sum; }
else if(N==2)
{
sum=(int)(M-(int)((M/N)+0.5)+1);
return sum;
}
else
return sum+count1(M,N-1);


}
int main()
{
   int t,m,n;
   cin>>t;
   vector<pair<int,int> >vec;
   for(int i=0;i<t;++i)
   {
   cin>>m>>n;
   vec.push_back(make_pair(m,n));

   }
   for(int j=0;j<vec.size();j++)
   {
   cout<<count1(vec[j].first,vec[j].second)<<endl;
   }

return 0;
}

[解决办法]

引用:

引用:算法错了。你如果听说过动态规划可以假设序列是递减的来保证一个组合只被统计一次再考虑。或者回去翻课本。以前好像没接触过动态规划的问题，刚找了下，研究下，

 其实10这种规模搜也可以过……做好判重。
[解决办法]
其实就是一个dp。。状态c[m][n][k]表示m个苹果n个盘子每个盘子最少放k个。。

#include <stdio.h>
#include <string.h>

int c[11][11][11];

int dfs(int m, int n, int k){
if(c[m][n][k] >= 0) return c[m][n][k];
if(m < n * k){
c[m][n][k] = 0;
return 0;
}
if(n == 1 && m >= k){
c[m][n][k] = 1;
return 1;
}
int cnt = 0;
for(int i = k; i <= m / n; ++i) cnt += dfs(m - i, n - 1, i);
c[m][n][k] = cnt;
return cnt;
}

int main(){
int t, m, n;
memset(c, -1, sizeof(c));
scanf("%d", &t);
while(t--){
scanf("%d%d", &m, &n);
printf("%d\n", dfs(m, n, 0));
}
return 0;
}

查看更多 下一篇