首页 > 代码库 > 快速切题 poj3744 概率dp 注意排序

快速切题 poj3744 概率dp 注意排序

#include <cstdio>#include <algorithm>using namespace std;int lame[11];void copy(double  des[2][2],double src[2][2]){    des[0][0]=src[0][0];des[0][1]=src[0][1];des[1][0]=src[1][0];des[1][1]=src[1][1];}void multi(double l[2][2],double r[2][2],double ans[2][2]){    double temp[4];    temp[0]=l[0][0]*r[0][0]+l[0][1]*r[1][0];    temp[1]=l[0][0]*r[0][1]+l[0][1]*r[1][1];    temp[2]=l[1][0]*r[0][0]+l[1][1]*r[1][0];    temp[3]=l[1][0]*r[0][1]+l[1][1]*r[1][1];    ans[0][0]=temp[0];ans[0][1]=temp[1];ans[1][0]=temp[2];ans[1][1]=temp[3];}void pow(double pro[2][2],double faim[2][2],int times){    double base[2][2] ;    copy(base,pro);    while(times>0){        if((times&1)==1)multi(base,faim,faim);        multi(base,base,base);        times>>=1;    }}int main(){    int n;    double p;    while(scanf("%d",&n)==1){        scanf("%lf",&p);        for(int i=0;i<n;i++)scanf("%d",lame+i);        sort(lame,lame+n);        double  faim[2][2];faim[1][0]=faim[0][1]=faim[1][1]=0;faim[0][0]=1;        double  pro[2][2];pro[0][0]=p;pro[0][1]=1-p;pro[1][0]=1;pro[1][1]=0;        int f=1;        for(int i=0;i<n;i++){            pow(pro,faim,lame[i]-f);            faim[0][0]=0;            f=lame[i];        }        faim[1][0]*=(1-p);        printf("%.7f\n",faim[1][0]);    }    return 0;}

  

快速切题 poj3744 概率dp 注意排序