考慮到此題麻煩了某hust大神&體現(xiàn)出了自己數(shù)學能力的欠缺 雖然最近一直比較忙 還是把這題的題解寫下來吧

首先看完數(shù)據(jù)范圍后 應該有不少人會反應到是$n^3$的DP 以$F[i][j]$表示從i到j這個區(qū)間所有情況之和

然后再枚舉中間點$k$從$F[i][k]$到$F[k+1][j]$轉移過來 但此題絕不是想到DP就可以了

--------------------------------------------------------------------------------------------------------------------------------

我們假設合并時 左區(qū)間所包含的情況為$a1.a2……ap$右區(qū)間所包含的情況為 $b1.b2……bq$

對于乘法運算 由于乘法分配率這個性質 直接把兩邊所有情況之和乘起來就行了?????????????????????????

對于加減法運算 左邊的區(qū)間每個元素出現(xiàn)的次數(shù)為q 右邊區(qū)間每個元素出現(xiàn)的次數(shù)為p

進一步 我們可以發(fā)現(xiàn) 出現(xiàn)次數(shù)p、q其實也就等于（區(qū)間長度-1）！ （感嘆號代表階乘 不要看錯= =）

看起來該做的事情已經(jīng)做完了 然而如果就這樣寫完代碼 會發(fā)現(xiàn)連樣例都過不了

---------------------------------------------------------------------------------------------------------------------------------

多想想之后 我們發(fā)現(xiàn)這樣一個問題 雖然合并時 左右區(qū)間都是確定的 然而達到同一個左右區(qū)間的方案并不是唯一的

我們先考慮一個比較小的情況 假設左區(qū)間通過$c1.c2$這兩個操作得到? 右區(qū)間通過$d1.d2$這兩個操作得到

那么我們只要保證同一區(qū)間內操作的有序性即可使得最后得到的兩個區(qū)間分別相同

比如$c1.c2.d1.d2$或$c1.d1.c2.d2$或……

這樣可能的情況就有$C_{4}^{2}$種 推廣到其他情況便是

C（（左區(qū)間長度-1）+（右區(qū)間長度-1），（左區(qū)間長度-1）） （注意到區(qū)間長度-1即為合并過程中的操作數(shù)）

于是這題便愉快地解決了

#include <bits/stdc++.h> using namespace std; const int N=110,MOD=1e9+7; long long f[N][N],fac[N],c[N][N]; char s[N]; int n; void prepare() {fac[0]=1;for(int i=1;i<=100;++i)fac[i]=fac[i-1]*i%MOD;c[0][0]=1;for(int i=1;i<=100;++i){c[i][0]=1;for(int j=1;j<=i;++j)c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;} } void work() {for(int i=1;i<=n;++i){scanf("%lld",&f[i][i]);for(int j=i+1;j<=n;++j)f[i][j]=0;}scanf("%s",&s[1]);for(int len=2;len<=n;++len)for(int i=1;i+len-1<=n;++i){int j=i+len-1;for(int k=i;k<j;++k){if(s[k]=='*')f[i][j]+=f[i][k]*f[k+1][j]%MOD*c[j-i-1][k-i];else if(s[k]=='+')f[i][j]+=(f[i][k]*fac[j-k-1]+f[k+1][j]*fac[k-i])%MOD*c[j-i-1][k-i];elsef[i][j]+=(f[i][k]*fac[j-k-1]-f[k+1][j]*fac[k-i])%MOD*c[j-i-1][k-i];f[i][j]%=MOD;}}//for(int i=1;i<=n;++i)// for(int j=i;j<=n;++j)// printf("%d %d %lld\n",i,j,f[i][j]);printf("%lld\n",(f[1][n]+MOD)%MOD);} int main() {prepare();while(~scanf("%d",&n))work();return 0; }

?

轉載于:https://www.cnblogs.com/sagitta/p/4741268.html

總結

以上是生活随笔為你收集整理的hdu 5396 Expression的全部內容，希望文章能夠幫你解決所遇到的問題。

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