首页 > 代码库 > UVA 10081 Tight numbers(POJ 2537)
UVA 10081 Tight numbers(POJ 2537)
直接看代码就OK。思路比较简单。就是注意概率要在转移过程中算出来。不能算成成立的方案书除以总方案数(POJ的这道题可以这么干。数据很水么。另外POJ要用%.5f,%.5lf 会WA。)
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}double dp[105][15];int N,K;void slove(){ if (K <= 1) {puts("100.00000");return;} for (int i = 0 ;i < 105; i++) for (int j = 0;j <15; j++) dp[i][j]=0.0; for (int i = 0 ;i <= K; i++) dp[1][i]=100.0/(double)(K+1); for (int i = 2; i <= N; i++) { dp[i][0] = 1.0/(double)(K+1) * ( dp[i-1][0] + dp[i-1][1]); for (int j = 1; j <= K ; j++) { if (j == K) dp[i][j] = 1.0/(double)(K+1) * (dp[i-1][K] + dp[i-1][K-1]); else dp[i][j] = 1.0/(double)(K+1) * (dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]); } } double ans=0.0; for (int i = 0 ;i <= K; i ++) ans+=dp[N][i]; printf("%.5lf\n",ans);}int main(){ while (scanf("%d%d",&K,&N)!=EOF) slove(); return 0;}
UVA 10081 Tight numbers(POJ 2537)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。