[POJ1664]放苹果(动态规划)
2024-09-02 08:55:05
[POJ1664]放苹果
Description
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
Input
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
Output
对输入的每组数据M和N,用一行输出相应的K。
Sample Input
1
7 3
Sample Output
8
考虑dp
dp[i][j]表示前i个苹果放入前j个盘子中的方案数
因为可以有盘子不放苹果
当i<j时,dp[i][j]=dp[i][i] (盘子和苹果均为相同的)
当i>=j时,此时可能盘子上都有苹果,我们把每个盘子上都拿走一个苹果,方案数不会变。(很妙啊)
\[dp[i][j]=dp[i-j][j]
\]
\]
也可能盘子上没有苹果
\[dp[i][j]=dp[i][j-1]
\]
\]
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[15][15];
void work(){
cin>>n>>m;
for(int i=0;i<=m;i++)dp[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i<j)dp[i][j]=dp[i][i];
else dp[i][j]=dp[i-j][j]+dp[i][j-1];
}
}printf("%d\n",dp[n][m]);
}
int main(){
ios::sync_with_stdio(false);
int t;cin>>t;
while(t--)work();return 0;
}
最新文章
- V4L2框架分析学习二
- ASP.NET MVC 静态资源打包和压缩问题小记
- grunt 使用
- 【数论】二进制GCD
- git_sop 脚本使用说明
- HBase分享会议笔记
- SUN dataset图像数据集下载
- POJ 1251 &;&; HDU 1301	 Jungle Roads (最小生成树)
- 在MAC下调试运行暗黑全世界客户端及部分代码注解(基于Firefly)
- javascript 读取内联之外的样式(style、currentStyle、getComputedStyle区别介绍) (转载)
- WPF之DataGrid应用(转)
- RelativeLayout的属性详解
- PAT (Advanced Level) 1059. Prime Factors (25)
- python 特殊方法实例
- Tomcat性能调优-JVM监控与调优
- C++读写图片数据转成Base64格式的一种方法
- maven名词解释
- beta 圆桌 3
- 【刷题】LOJ 6007 「网络流 24 题」方格取数
- Java 内存模型_2