POJ1664:放苹果(线性dp)
2024-10-19 23:27:08
题目: http://poj.org/problem?id=1664
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
递推求解
如果m = 1,将一个苹果放在n个盘子里,因为511和151属于同一种方法,所以只有一种放法f(1,n) = 1;
如果n = 1,将m个苹果放在1个盘子里,只有一种方法f(m,1) = 1;
如果m=n, 分为两种情况1、每个盘子里都放苹果共有一种放法,2、至少有一个盘子里不放苹果 即与放在n-1个盘子里放法相同 所以f(m,n) = f(m,n-1)+1;
如果m > n, 同样2种情况1、每个盘子里都放苹果 先把n个苹果抽出来放进n个盘子里f(n,n) 还剩m-n个苹果放进n个盘子里f(m-n,n)*1 2、 至少一个盘子里不放 与上一个相同 所以总结果f(m,n) = f(m,n-1)+f(m-n,n);
如果m<n , 等于把把m个苹果放进m个盘子里 f(m,n) = f(m,m);
代码如下:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,m,dp[][];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
dp[i][]=;
for(int i=;i<=n;i++)
dp[][i]=;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
{
if(i==j)
dp[i][j]=+dp[i][j-];
if(i>j)
dp[i][j]=dp[i-j][j]+dp[i][j-];
if(i<j)
dp[i][j]=dp[i][i];
}
}
printf("%d\n",dp[m][n]);
}
return ;
}
最新文章
- linux 安装 nginx 及反向代理配置
- 可爱的Python_课后习题_CDay−4 可用的首个Python 脚本
- WCF关于svcutil生成关于绑定出现 元数据包含无法解析的引用的解决方案
- MyBatis学习 之 一、MyBatis简介与配置MyBatis+Spring+MySql
- nyoj 14 会场安排问题
- 在 Ubuntu 16.04 中安装谷歌 Chrome 浏览器
- Ubuntu全新系统一些配置
- 10.18 noip模拟试题
- /etc/ld.so.conf详解
- windows cmd: 增强windows命令行
- 从 RequireJs 源码剖析脚本加载原理
- 使用binlog2sql做数据恢复的简单示例
- day13_DOM
- weui复选框无法传值
- playframework 一步一步来 之 日志 (三)
- 用rpm命令安装定时器crontab
- iOS-copy与mutableCopy浅析
- Kubernetes集群安全配置案例
- python 文件读取方法详解
- mybatis 批量增加 Parameter &#39;__frch_item_0&#39; not found. Available parameters are [list]