本文主要是介绍uva 10118 dP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给4列篮子，每次从某一列开始无放回拿蜡烛放入篮子里，并且篮子最多只能放5支蜡烛，数字代表蜡烛的颜色。
当拿出当前颜色的蜡烛在篮子里存在时，猪脚可以把蜡烛带回家。
问最多拿多少只蜡烛。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>#define LL long longusing namespace std;
const int maxn = 40 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n;
int pile[4][maxn];
int dp[maxn][maxn][maxn][maxn];
int top[4];
bool color_hash[20 + 10];int dfs(int dep)
{if (dep == -1)return 0;int& res = dp[top[0]][top[1]][top[2]][top[3]];if (res)return res;if (dep == 5)return res = 0;///for (int i = 0; i < 4; i++){if (top[i] == n)continue;int color = pile[i][top[i]];top[i]++;if (color_hash[color]){color_hash[color] = false;res = max(res, dfs(dep - 1) + 1);color_hash[color] = true;}else{color_hash[color] = true;res = max(res, dfs(dep + 1));color_hash[color] = false;}top[i]--;}return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (scanf("%d", &n) && n){for (int j = 0; j < n; j++){for (int i = 0; i < 4; i++){scanf("%d", &pile[i][j]);}}memset(dp, 0, sizeof(dp));memset(color_hash, false, sizeof(color_hash));memset(top, 0, sizeof(top));printf("%d\n", dfs(0));}return 0;
}
这篇关于uva 10118 dP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
