钉子和小球

钉子和小球

又是动态规划，而且又是不会~其实这道题再仔细想一想还是可以做的，比之前的简单一些，大致的思路：假设从 dp[i][j] 开始，如果这里有钉子，那么可以落到下一行的两边可能性各为二分之一，也即 dp[i + 1][j] += (dp[i][j] / 2) 和 dp[i + 1][j + 1] += (dp[i][j] / 2)，如果是空的呢，就是直接落在正下方了，注意 i 和 j 的变化就好啦：dp[i+2][j+1]+=dp[i][j]，然后抓住细节就不难了（细节写在注释中了~）：

//动态规划（规律比之前好找一些~） 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll sumdp, mdp;//结果为 "mdp/sumdp" 的最简形式 
int n, m;
char a[60];
int flag[60][60];//将输入的字符信息转化为 0 或 1 
ll dp[60][60];
ll gcd(ll a, ll b) {//最大公因数 return b == 0 ? a : gcd(b, a % b);
}
int main() {while (scanf("%d%d", &n, &m) != EOF) {//一开始输入忘加 & 了！导致“Runtime error”，罪过啊~ sumdp = 0;mdp = 0;//细节：每一轮输入都要重新初始化！下面的 dp 归零也是如此 for (int i = 0;i < n;i++) {for (int j = 0;j <= i;j++) {//第 i 行有 i+1 个字符（i 从 0 开始） scanf("%s", a);//一次读入一个字符 if (a[0] == '*') flag[i][j] = 1;//信息转化 else flag[i][j] = 0;}}memset(dp, 0, sizeof(dp));dp[0][0] = 1;//初始化 for (int i = 0;i < n;i++) dp[0][0] *= 2;//这里放大为 2^n ,用整数更加好算（有除以 2 的步骤保证仍为整数） for (int i = 0;i < n;i++) {for (int j = 0;j <= i;j++) {if (flag[i][j]) {dp[i + 1][j] += (dp[i][j] / 2);dp[i + 1][j + 1] += (dp[i][j] / 2);}else dp[i + 2][j + 1] += dp[i][j];}}for (int i = 0;i < n + 2;i++) sumdp += dp[n][i];mdp = dp[n][m];cout << mdp / (gcd(mdp, sumdp)) << '/' << sumdp / gcd(mdp, sumdp) << endl;}return 0;
}

老生常谈加油，今天老生加油了吗？