【总结】一些简单dp题的口胡题解

bzoj2118 墨墨的等式
模意义下最短路

CF618F. Double Knapsack
$S1_i,S2_i$S1i​,S2i​分别表示$a,b$a,b的前缀和，设$S1_n\leq S2_n$S1n​≤S2n​。
对于每个$S1_i$S1i​，必然能找到一个$j$j，使得$0\leq S2_j-S1_i&lt;n$0≤S2j​−S1i​<n，设为$to_i$toi​。
由于$0\leq S2_{to_i}-S1_i&lt;n$0≤S2toi​​−S1i​<n，$0\leq i\leq n$0≤i≤n，取值有$n$n个，个数有$n+1$n+1个，根据抽屉原理必然有一段相同的。

HDU2191 单调队列优化多重背包：

 for(i=1;i<=n;i++){
            scanf("%d%d%d",&w,&v,&s);
            if(s>m/w)s=m/w;
            for(d=0;d<w;d++){
                he=ta=1;
                for(j=0;j<=(m-d)/w;j++){
                    int tmp=f[j*w+d]-v*j;
                    while(he<ta&&q[ta-1]<=tmp)--ta;
                    q[ta]=tmp,num[ta++]=j;
                    while(he<ta&&j-num[he]>s)++he;
                    f[j*w+d]=max(f[j*w+d],q[he]+v*j);
                }
            }
        }

广工oj1231 | 51nod 1821 tmk买礼物
将$a_i$ai​按升序排序，假设前$i$i个数可以凑出$[1,n]$[1,n]中所有数，则必须满足$a_{i+1}\leq n+1$ai+1​≤n+1(否则无法凑出$n+1$n+1)，且此时可以凑出$[1,n+a_i]$[1,n+ai​]中所有数。

bzoj 1419: Red is good
倒着$dp[i][j]$dp[i][j]表示还剩下$i$i张红牌，$j$j张黑牌时最优策略下平均能得到的钱数:$dp[i][j]=max(0,\frac{i}{i+j}(dp[i-1][j]+1)+\frac{j}{i+j}(dp[i][j-1]-1))$dp[i][j]=max(0,i+ji​(dp[i−1][j]+1)+i+jj​(dp[i][j−1]−1))。

bzoj 3566: [SHOI2014]概率充电器

正难则反,考虑容斥：设$f[i]$f[i]表示$i$i点不通电的概率，答案即为$\sum\limits_{i=1}^n 1-f[i]$i=1∑n​1−f[i]
设$p_i$pi​表示点$i$i直接充电的概率，$w_i$wi​表示点$i$i和父亲结点联通的概率。
首先考虑自己不通电加上所有$son_i$soni​不同点的概率：$f[i]=(1-p_i)\prod\limits_{j\in son_i}(1-(1-f[j])w_j)$f[i]=(1−pi​)j∈soni​∏​(1−(1−f[j])wj​)
再考虑$i$i的父亲$x$x对$i$i的贡献，除去$i$i后$x$x通电的概率$t=1-\frac{f[x]}{(1-(1-f[i])w_i)}$t=1−(1−(1−f[i])wi​)f[x]​，则$f[i]$f[i]需要再乘上$1-tw_i$1−twi​。
两遍$dfs$dfs即可。

bzoj 2510: 弱题
循环矩阵快速幂$O(n^2log)$O(n2log)
矩阵乘法$c[i+j]=a[i]\times b[j]$c[i+j]=a[i]×b[j](循环矩阵乘循环矩阵还是循环矩阵)