首页 > 代码库 > D. Caesar's Legions 背包Dp 递推DP
D. Caesar's Legions 背包Dp 递推DP
http://codeforces.com/problemset/problem/118/D
设dp[i][j][k1][k2]
表示,放了i个1,放了j个2,而且1的连续个数是k1,2的连续个数是k2
如果这样写,用dfs写是很简单的。但是超时,我记忆化不到
如果用递推写,对于每一个状态,更新到下一个状态。
如果放的是1,那么新的状态是dp[i + 1][j][k1 + 1][0]也就是,用多了一个1,而且连续的个数也增加了。同时,2的连续个数就打破了,变成了0
这种枚举旧状态,更新下一个状态的dp,以前比较排斥,一般都是dp[i][j] += dp[i - 1][j - 1]这样的,但是其实是一样的,也是不会有后效性
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> int n1, n2, k1, k2; int ans; const int MOD = 1e8; int dp[111][111][12][12]; void work() { cin >> n1 >> n2 >> k1 >> k2; dp[0][0][0][0] = 1; for (int i = 0; i <= n1; ++i) { for (int j = 0; j <= n2; ++j) { for (int h = 0; h <= k1; ++h) { for (int z = 0; z <= k2; ++z) { if (i != n1 && h != k1) { dp[i + 1][j][h + 1][0] += dp[i][j][h][z]; dp[i + 1][j][h + 1][0] %= MOD; } if (j != n2 && z != k2) { dp[i][j + 1][0][z + 1] += dp[i][j][h][z]; dp[i][j + 1][0][z + 1] %= MOD; } } } } } int ans = 0; for (int i = 0; i <= k1; ++i) { for (int j = 0; j <= k2; ++j) { ans += dp[n1][n2][i][j]; if (ans >= MOD) ans -= MOD; } } cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
D. Caesar's Legions 背包Dp 递推DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。