想狀態和釘子的位置如何匹配想了半天。。。后來發現不是一樣的嗎$qwq$

---

?

思路：當然是$DP$啦

提交：>5次（以為無故$RE$，實則是先乘后除爆了$long\space long$）

題解：

若有釘子，左右各乘$\frac{1}{2}$轉移，否則，向下兩層直接轉移。

對于分數，分別維護分子和分母，然后加起來的時候，記著一定要寫成

up[i][j]=up[i][j]*(b/G)+a*(dn[i][j]/G); dn[i][j]=dn[i][j]*(b/G);

而非

up[i][j]=up[i][j]*b/G+a*dn[i][j]/G; dn[i][j]=dn[i][j]*b/G;

（好吧也是我傻$qwq$）

代碼：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define ull unsigned long long #define ll long long #define R register ll #define pause (for(R i=1;i<=10000000000;++i)) #define In freopen("NOIPAK++.in","r",stdin) #define Out freopen("out.out","w",stdout) namespace Fread { inline int g() {R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } inline bool isempty(const char& ch) {return (ch<=36||ch>=127);} inline void gs(char* s) {register char ch; while(isempty(ch=getchar()));do *s++=ch; while(!isempty(ch=getchar())); } } using Fread::g; using Fread::gs; namespace Luitaryi { const int N=60; int n,m; ll up[N][N],dn[N][N]; bool w[N][N]; inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a; } inline void add(int i,int j,ll a,ll b) {R G=gcd(dn[i][j],b);up[i][j]=up[i][j]*(b/G)+a*(dn[i][j]/G);dn[i][j]=dn[i][j]*(b/G);G=gcd(up[i][j],dn[i][j]); if(G) up[i][j]/=G,dn[i][j]/=G; } inline void main() {n=g(),m=g()+1;for(R i=1;i<=n;++i) for(R j=1;j<=i;++j) { register char ch;while(ch=getchar(),ch!='*'&&ch!='.'); w[i][j]=(ch=='*');up[i][j]=0,dn[i][j]=1;} for(R i=1;i<=n;++i) up[n+1][i]=0,dn[n+1][i]=1;up[1][1]=dn[1][1]=1;for(R i=1;i<=n;++i) for(R j=1;j<=i;++j) {R a=up[i][j],b=dn[i][j];if(w[i][j]) {if(a%2==0) a/=2; else b*=2;add(i+1,j,a,b),add(i+1,j+1,a,b);} else add(i+2,j+1,a,b);} printf("%lld/%lld",up[n+1][m],dn[n+1][m]);} } signed main() {Luitaryi::main(); }

---

2019.07.17

轉載于:https://www.cnblogs.com/Jackpei/p/11204464.html

總結

以上是生活随笔為你收集整理的BZOJ 1867 [Noi1999]钉子和小球 DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。