1.POJ 3744 Scout YYF I
经典的dp模型，但是要用到快速矩阵幂加速，分段的思想
# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <iostream>
using namespace std; int mines[]; void matrixMulti(double a[][], double b[][]){
double i,j,k,l;
i = a[][]*b[][]+a[][]*b[][];
j = a[][]*b[][]+a[][]*b[][];
k = a[][]*b[][]+a[][]*b[][];
l = a[][]*b[][]+a[][]*b[][];
a[][]=i,a[][]=j,a[][]=k,a[][]=l;
} double quickPow(const double p, int x){
if(x == -){
return 1.0;
}
double a[][] = {, , -p, p}, res[][] = {,,,};
while(x){
//printf("this 3\n");
if(x&){
matrixMulti(res, a);
}
x/=;
matrixMulti(a,a);
}
return res[][]*(-p);
} int main(){
int num;
double p, result;
while(scanf("%d%lf",&num, &p) != EOF){
memset(mines, , sizeof(mines));
for(int i = ; i <= num; ++i){
scanf("%d", mines + i);
}
if(mines[] == ){
printf("%.7f\n", 0.0);
continue;
}
mines[] = ;
result = 1.0;
sort(mines, mines+num+);
for(int i = ; i <= num; ++i){
result *= quickPow(p, mines[i] - mines[i - ] - );
}
if(result < ){
result = ;
}
if(result > ){
result =;
}
printf("%.7f\n", result);
}
return ;
}
心得：1.dp[i]=dp[i-2]*(1-p)+dp[i-1]*p,其实就是连续跟1-p/p相乘，自然想到矩阵加速。2.快速幂的思想，将O(n)降成O(lg(n))。
3.[0, 1; 1-p, p] * [dp[i-2]; dp[i-1]] = [dp[i-1]; dp[i]],然后变成幂运算之后就可以加速了。多次乘以相同的数值其实就是幂运算（一个数就是整数幂，多个数的式子就是矩阵幂）
2.POJ 2096 Collecting Bugs
经典的dp求期望的题，注意理解反向求期望的思想，以及C++整数除法跟数学上的除法的区别（他是下取整的）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std; double dp[][];
int main()
{
int n, s;
double a, b, c, d;
//cout << sizeof(dp);
while(scanf("%d%d", &n, &s) != EOF){
memset(dp, , sizeof(dp));
for(int i = n; i >= ; --i){
for(int j = s; j >= ; --j){
if(i==n&&j==s)continue;
a = 1.0*(n-i)/n*j/s;
b = 1.0*i/n*(s-j)/s;
c = 1.0*i/n*j/s;
d = 1.0*(n-i)/n*(s-j)/s;
dp[i][j] = (a * dp[i+][j]+b*dp[i][j+]+d*dp[i+][j+] + 1.0)/(1.0-c);
}
}
printf("%.4f\n",dp[][]);
}
return ;
}
心得：1.C++整数除法跟数学上的除法的区别（他是下取整的）2.反向求期望的思想跟期望的性质E(aA+bB+....) = aE(A)+bE(B)+.....3.本题的递推公式需要变形计算一下：dp[i][[j] = a*dp[i+1][j]+b*dp[i][j]+c*dp[i][j+1]+d*dp[i+1][j+1]+14.动态规划矩阵的边界条件的控制。容易变坑，尤其是2维情况下