2012-A3-0008
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意：一开始有(x,,0,,,y,,0,,),依次经过n个操作，第i次可以(x,,i,,,y,,i,,)=((1-p,,i,,(1-b,,i,,/a,,i,,))x,,i-1,,+b,,i,,*y,,i-1,,,p,,i,,/a,,i,,*x,,i-1,,+y,,i-1,,),
其中p,,i,,为[0,1]中一个实数，a,,i,,,b,,i,,为题目中给定的，求x,,n,,的最大值。
首先把递推式写成矩阵形式 D,,i,, = [ [1-(1-b,,i,,/a,,i,,)*p,,i,, , b,,i,,],[p,,i,,/a,,i,, ,1]]
[x,,n,,,y,,n,,]^T^=D,,n,,*D,,n-1,,*...*D,,2,,*D,,1,,*[x,,0,,,y,,0,,]^T^
对于其中某一个决策，分解 D,,i,, = (1-p,,i,,)*[[1,b,,i,,],[0,1]] + p,,i,,*[[b,,i,,/a,,i,,,b,,i,,],[1/a,,i,,,1]] = (1-p,,i,,)*D,,i0,, + p,,i,,*D,,i1,,
由矩阵乘法的结合律和左右分配律， [x,,n,,,y,,n,,]^T^
= D,,n,,*...*Di*...*D,,1,,*[x,,0,,,y,,0,,]^T^
= D,,n,,*...*((1-p,,i,,)*D,,i0,, + p,,i,,*D,,i1,,)*...*D,,1,,*[x,,0,,,y,,0,,]^T^
= (1-p,,i,,)*( D,,n,,*...*D,,i0,,*...*D,,1,,)*[x,,0,,,y,,0,,]^T^+p,,i,,*( D,,n,,*...*D,,i1,,*...*D,,1,,)*[x,,0,,,y,,0,,]^T^
为了使x,,n,,最大,对于任一决策D,,i,,, 如果以D,,i0,,,D,,i1,,代替D,,i,,的结果不一样，都可以单调调整p,,i,,使结果单调变大或变小，所以x,,n,,极大值时p,,i,,非0即1
观察 [x,,n,,,y,,n,,]^T^ = D,,n...1,, * ([x,,0,,, 0]^T^ +[0, y,,0,,]^T^) = x,,0,,*D,,n..1,,*[1, 0]^T^ + y,,0,,*D,,n..1,,*[0, 1]^T^
[1, 0]^T^要使D,,n..1,,第一行第一列的结果最大，[0, 1]^T^要使第一行第2列最大，
又由于上述所有矩阵中的元素都是正数，每个D,,i,,决策中第2列都是b,,i,,和 1
从左向右结合计算乘积，每次第2列的结果都是由前面的决策决定的，所以第一列最大就可以导致第2列最大
于是只要存第一行的结果就可以了，并且只要保证第一行的第一列的结果最大，就会使总结果最大.
从矩阵中分离出来的结果，第一行第一列，只有两种决策，两种里选个大的就可以了。
{{{
#include<cstdio>
#include<algorithm>
typedef double real;
real a[102400],b[102400],d[2][2];
int main(){
for(size_t n,X0,Y0;3==scanf("%u%u%u",&n,&X0,&Y0);){
for(size_t i=0;i<n;++i)scanf("%lf%lf",a+i,b+i);
d[n&1][0]=1;d[n&1][1]=0;
for(size_t i=n,p,q;i--;){
p=i&1;q=!p;
d[p][0]=std::max(d[q][0]*b[i]/a[i]+d[q][1]/a[i],d[q][0]);
d[p][1]=d[q][1]+d[q][0]*b[i];
}
printf("%.2lf\n",d[0][0]*X0+d[0][1]*Y0);
}
return 0;
}
}}}题意：一开始有(x0,y0),依次经过n个操作，第i次可以(xi,yi)=((1-pi(1-bi/ai))xi-1+bi*yi-1,pi/ai*xi-1+yi-1),
其中pi为[0,1]中一个实数，ai,bi为题目中给定的，求xn的最大值。
首先把递推式写成矩阵形式 Di = [ [1-(1-bi/ai)*pi , bi],[pi/ai ,1]]
[xn,yn]T=Dn*Dn-1*...*D2*D1*[x0,y0]T
对于其中某一个决策，分解 Di = (1-pi)*[[1,bi],[0,1]] + pi*[[bi/ai,bi],[1/ai,1]] = (1-pi)*Di0 + pi*Di1
由矩阵乘法的结合律和左右分配律， [xn,yn]T
= Dn*...*Di*...*D1*[x0,y0]T
= Dn*...*((1-pi)*Di0 + pi*Di1)*...*D1*[x0,y0]T
= (1-pi)*( Dn*...*Di0*...*D1)*[x0,y0]T+pi*( Dn*...*Di1*...*D1)*[x0,y0]T
为了使xn最大,对于任一决策Di, 如果以Di0,Di1代替Di的结果不一样，都可以单调调整pi使结果单调变大或变小，所以xn极大值时pi非0即1
观察 [xn,yn]T = Dn...1 * ([x0, 0]T +[0, y0]T) = x0*Dn..1*[1, 0]T + y0*Dn..1*[0, 1]T
[1, 0]T要使Dn..1第一行第一列的结果最大，[0, 1]T要使第一行第2列最大，
又由于上述所有矩阵中的元素都是正数，每个Di决策中第2列都是bi和 1
从左向右结合计算乘积，每次第2列的结果都是由前面的决策决定的，所以第一列最大就可以导致第2列最大
于是只要存第一行的结果就可以了，并且只要保证第一行的第一列的结果最大，就会使总结果最大.
从矩阵中分离出来的结果，第一行第一列，只有两种决策，两种里选个大的就可以了。
#include<cstdio>
#include<algorithm>
typedef double real;
real a[102400],b[102400],d[2][2];
int main(){
for(size_t n,X0,Y0;3==scanf("%u%u%u",&n,&X0,&Y0);){
for(size_t i=0;i<n;++i)scanf("%lf%lf",a+i,b+i);
d[n&1][0]=1;d[n&1][1]=0;
for(size_t i=n,p,q;i--;){
p=i&1;q=!p;
d[p][0]=std::max(d[q][0]*b[i]/a[i]+d[q][1]/a[i],d[q][0]);
d[p][1]=d[q][1]+d[q][0]*b[i];
}
printf("%.2lf\n",d[0][0]*X0+d[0][1]*Y0);
}
return 0;
}