URAL 1114 Boxes（简单dp）

题目链接；
URAL 1114 Boxes
题意：
有$n$个箱子，和$A$个红球，$B$个蓝球。每个箱子可以选择放任意个红球和蓝球，而且不必放完所有的球。求所有的放置方案数。
数据范围：$1\leq N \leq 20, 0\leq A\leq 15,0\leq B\leq 15$.
分析：
简单$dp$。
用$dp[i][j][k]$表示前$i$个箱子一共放置$j$个红球和$k$个蓝球的方案数。
状态转移方程：

$$dp[i][j][k]=\sum_{j'=0}^{j'\leq j}\sum_{k'=0}^{k'\leq k}dp[i-1][j'][k']$$
初始化： $dp[0][0][0]=1$。
答案就是：

$$Ans=\sum_{j=0}^{j\leq A}\sum_{k=0}^{k\leq B}dp[n][j][k]$$
注意数据会超 $long \ long$。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 25;
const int MAX_M = 20;
const ll  BASE = (ll)(1e9);
const int size = 10;ll dp[MAX_N][MAX_M][MAX_M][size];void solve(int n, int A, int B)
{memset(dp, 0, sizeof(dp));dp[0][0][0][0] = 1;for(int i = 1; i <= n; ++i) {for(int j = 0; j <= A; ++j) {for(int k = 0; k <= B; ++k) {for(int jj = 0; jj <= j; ++jj) {for(int kk = 0; kk <= k; ++kk) {for(int t = 0; t < size - 1; ++t) {dp[i][j][k][t] += dp[i - 1][jj][kk][t];dp[i][j][k][t + 1] += dp[i][j][k][t] / BASE;dp[i][j][k][t] %= BASE;//if(dp[i][j][k][t]) printf("dp[%d][%d][%d][%d] = %lld\n", i, j, k, t, dp[i][j][k][t]);}}}//printf("dp[%d][%d][%d] = %lld\n", i, j, k, dp[i][j][k]);}}}ll ans[size];memset(ans, 0, sizeof(ans));for(int i = 0; i <= A; ++i) {for(int j = 0; j <= B; ++j) {for(int t = 0; t < size - 1; ++t) {ans[t] += dp[n][i][j][t];ans[t + 1] += ans[t] / BASE;ans[t] %= BASE;}}}int st = 0;for(int i = size - 1; i >= 0; --i) {if(ans[i] > 0) {printf("%lld", ans[i]);st = i;break;}}for(int i = st - 1; i >= 0; --i) {printf("%09lld", ans[i]);}printf("\n");
}int main()
{int n, A, B;while(~scanf("%d%d%d", &n, &A, &B)) {solve(n, A, B);}return 0;
}