放苹果
把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
Source
题目类型：线性DP
算法分析：dp[i][j]为j的i次划分，初始化dp[0][0] = 1，状态转移方程为dp[i][j] = dp[i][j-i] + dp[i-1][j]，计算后查表输出即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
/************************************************** filename :d.cpp author :maksyuki created time :2017/3/3 16:59:59 last modified :2017/3/3 17:06:16 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CPPFF ifstream cin ("in") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int dp[20][20]; int main() { //CFF; //CPPFF; dp[0][0] = 1; for(int i = 1; i <= 12; i++) for(int j = 0; j <= 12; j++) if(j - i >= 0) dp[i][j] = dp[i][j-i] + dp[i-1][j]; else dp[i][j] = dp[i-1][j]; int t; scanf("%d", &t); while(t--) { int N, M; scanf("%d%d", &M, &N); printf("%d\n", dp[N][M]); } return 0; } |
- « 上一篇：poj1414
- poj1953：下一篇 »