[Usaco2008 Oct]笨重的石子 DP

本文主要是介绍[Usaco2008 Oct]笨重的石子 DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。 问题给出三个骰子的面数，让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就输出小的那一个。

这题按理来说用随机算法也应该能过。

不过我试了却没过。

标准的算法是算出组成每个数的方案数， 然后最大的即为所求

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
#include <set>
#define MAXN 51111
#define MAXM 555
#define INF 1000000007
using namespace std;
int f[4][86];
int main()
{int a, b, c;scanf("%d%d%d", &a, &b, &c);for(int i = 1; i <= a; i++) f[1][i] = 1;for(int i = 1; i <= a + b; i++)for(int j = 1; j <= b; j++)if(i > j) f[2][i] += f[1][i - j];for(int i = 1; i <= a + b + c; i++)for(int j = 1; j <= c; j++)if(i > j) f[3][i] += f[2][i - j];int ans = 0;for(int i = 1; i <= a + b + c; i++)if(f[3][ans] < f[3][i])ans = i;printf("%d\n", ans);return 0;
}

这篇关于[Usaco2008 Oct]笨重的石子 DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---