DZY loves balls combination dp

6月 5 2015

python 如何按照数组个数打印list的元素

L=[1,2,3,4,5]
print ‘ ‘.join([str(i) for i in L])
join 需要是存string的list也即每个join对象是string

[1,2,3,4,5] -> [‘1’, ‘2’, ‘3’, ‘4’, ‘5’]
一句话将一个list的里面每个元素都进行转化 [str(i) for i in L]

latex
公式自动换行，但是还是一个公式用split，然后里面\

\begin{equation}\label{eq:28}
\begin{split}
    h_{0}\sim P(h|v_{0})\\
    v_{1}\sim P(v|h_{0})\\
    h_{1}\sim P(h|v_{1})\\
    v_{2}\sim P(v|h_{1})\\
    h_{l}\sim P(h|v_{l})\\
    v_{l+1}\sim P(v|h_{l})
\end{split}
\end{equation}

今天做了一题，对于被8整除的数，性质就是最后三位被8整除。

之前只知道被2整除看各位，被3整除看数字和是否被3整除

知道这个性质之后可以n^3的暴力写CF306Div2ProC了

http://acm.hdu.edu.cn/showproblem.php?pid=5194

BC35ProA的一题

当年由于数据小打表过的。昨天蛋哥提到了一道他本科离散数学的一道题，于是我想到了这题

然后想了一下DP的思考过程。哎，大神们都是直接给出DP方程，却把最重要的思维过程，毕竟谁都是曾经弱过的啊，一开始不可能一下就想到了定义dp状态，除非看答案。

首选是直接按照问题来定义dp，dpij表示i个1，j个0的所有排列中’01’的个数
然后看dp-1j, dpij-1, dpi-1j-1, 一般都是看这几个

如果抽象思维不够快，可以举小数据的例子，例如n=2,m=2
一举例发现特别快，就是最后一位是0，那么就是dpij-1, 最后一位是1就是dpi-1j, 然后还有倒数第二个是0和最后1组成的，也就是n-2个1 m-2个0里面的组合数，C(n+m-2, n-1)

因此dp[i][j]=dp[i][j-1]+dp[i-1][j]+C(n+m-2, n-1)

对于初始条件，二维的最好方法就是写个二维表格，然后看0行0列举例

n<1 || m<1时，肯定是0个了，所以全是0

另外算组合数要用Cij=Ci-1j-1+Ci-1j这个公式

因为直接算可能分子分母会上溢出，这是和数学的本质区别，算法强调计算性。

int C[30][30], dp[30][30];
void Calc()
{
    memset(C, 0, sizeof C);
    for(int i=0;i<=24;i++) C[i][0]=1;
    for(int i=1;i<=24;i++) for(int j=1;j<=24;j++)
        C[i][j]=C[i-1][j-1]+C[i-1][j];
}
int main()
{
/*
#ifndef ONLINE_JUDGE
    freopen ("in.txt" , "r" , stdin);
    freopen ("out.txt" , "w" , stdout);
#endif
*/
    Calc();
    while(cin>>n>>m)
    {
        memset(dp, 0 ,sizeof dp);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
            dp[i][j]=dp[i][j-1]+dp[i-1][j]+C[i+j-2][i-1];
        int gcd=GCD(dp[n][m], C[n+m][n]);
        cout<<dp[n][m]/gcd<<'/'<<C[n+m][n]/gcd<<endl;
    }
    return 0;
}

另外再附上一题，长为n的01序列里’01’出现的次数

dpi=2*dpi-1+2^(i-2)
参数为1个的话，更加好思考，

分成两块，一块是完全由n-1长串里01的个数决定，最后一位0或1，2*dpn-1
一块是由n-1长串和第n个共同贡献的01，也即最后两位是01，也即n-2长串的组合数2^(n-2)

再用plug-in方法直接算通项 dpn=(n-1)*2^(n-2)

Posted by richard爱闹 - 6月 5 2015
如需转载，请注明：本文来自 Richard

留言