BestCoder Round #63 (div.2)

感觉有些无聊的比赛。

暴力枚举下就行

简单的dp，但是wa了一发后就去先把C做了，然后发现如果输入的100个数，是如1，2，3，4,...,100，然后k=50,个数为c(100,50).果断大数。用了个c++的大数模板，感觉用的很爽。

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define DIGIT   4      //四位隔开,即万进制

#define DEPTH   10000        //万进制

#define MAX     100    //题目最大位数/4，要不大直接设为最大位数也行

typedef int bignum_t[MAX+];

/************************************************************************/

/* 读取操作数，对操作数进行处理存储在数组里                             */

/************************************************************************/

int read(bignum_t a,istream&is=cin)

{

    char buf[MAX*DIGIT+],ch ;

    int i,j ;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>buf))return  ;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

        ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

        for(a[i]=,j=;j<DIGIT;j++)

            a[i]=a[i]*+buf[i*DIGIT--j]-'' ;

    for(;!a[a[]]&&a[]>;a[]--);

    return  ;

}

void write(const bignum_t a,ostream&os=cout)

{

    int i,j ;

    for(os<<a[i=a[]],i--;i;i--)

        for(j=DEPTH/;j;j/=)

            os<<a[i]/j% ;

}

int comp(const bignum_t a,const bignum_t b)

{

    int i ;

    if(a[]!=b[])

        return a[]-b[];

    for(i=a[];i;i--)

        if(a[i]!=b[i])

            return a[i]-b[i];

    return  ;

}

int comp(const bignum_t a,const int b)

{

    int c[]=

    {

    }

    ;

    for(c[]=b;c[c[]]>=DEPTH;c[c[]+]=c[c[]]/DEPTH,c[c[]]%=DEPTH,c[]++);

    return comp(a,c);

}

int comp(const bignum_t a,const int c,const int d,const bignum_t b)

{

    int i,t=,O=-DEPTH* ;

    if(b[]-a[]<d&&c)

        return  ;

    for(i=b[];i>d;i--)

    {

        t=t*DEPTH+a[i-d]*c-b[i];

        if(t>)return  ;

        if(t<O)return  ;

    }

    for(i=d;i;i--)

    {

        t=t*DEPTH-b[i];

        if(t>)return  ;

        if(t<O)return  ;

    }

    return t> ;

}

/************************************************************************/

/* 大数与大数相加                                                       */

/************************************************************************/

void add(bignum_t a,const bignum_t b)

{

    int i ;

    for(i=;i<=b[];i++)

        if((a[i]+=b[i])>=DEPTH)

            a[i]-=DEPTH,a[i+]++;

    if(b[]>=a[])

        a[]=b[];

    else

        for(;a[i]>=DEPTH&&i<a[];a[i]-=DEPTH,i++,a[i]++);

    a[]+=(a[a[]+]>);

}

/************************************************************************/

/* 大数与小数相加                                                       */

/************************************************************************/

void add(bignum_t a,const int b)

{

    int i= ;

    for(a[]+=b;a[i]>=DEPTH&&i<a[];a[i+]+=a[i]/DEPTH,a[i]%=DEPTH,i++);

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

}

/************************************************************************/

/* 大数相减(被减数>=减数)                                               */

/************************************************************************/

void sub(bignum_t a,const bignum_t b)

{

    int i ;

    for(i=;i<=b[];i++)

        if((a[i]-=b[i])<)

            a[i+]--,a[i]+=DEPTH ;

    for(;a[i]<;a[i]+=DEPTH,i++,a[i]--);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数减去小数(被减数>=减数)                                           */

/************************************************************************/

void sub(bignum_t a,const int b)

{

    int i= ;

    for(a[]-=b;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void sub(bignum_t a,const bignum_t b,const int c,const int d)

{

    int i,O=b[]+d ;

    for(i=+d;i<=O;i++)

        if((a[i]-=b[i-d]*c)<)

            a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH ;

    for(;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数相乘，读入被乘数a，乘数b，结果保存在c[]                          */

/************************************************************************/

void mul(bignum_t c,const bignum_t a,const bignum_t b)

{

    int i,j ;

    memset((void*)c,,sizeof(bignum_t));

    for(c[]=a[]+b[]-,i=;i<=a[];i++)

        for(j=;j<=b[];j++)

            if((c[i+j-]+=a[i]*b[j])>=DEPTH)

                c[i+j]+=c[i+j-]/DEPTH,c[i+j-]%=DEPTH ;

    for(c[]+=(c[c[]+]>);!c[c[]]&&c[]>;c[]--);

}

/************************************************************************/

/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数                   */

/************************************************************************/

void mul(bignum_t a,const int b)

{

    int i ;

    for(a[]*=b,i=;i<=a[];i++)

    {

        a[i]*=b ;

        if(a[i-]>=DEPTH)

            a[i]+=a[i-]/DEPTH,a[i-]%=DEPTH ;

    }

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void mul(bignum_t b,const bignum_t a,const int c,const int d)

{

    int i ;

    memset((void*)b,,sizeof(bignum_t));

    for(b[]=a[]+d,i=d+;i<=b[];i++)

        if((b[i]+=a[i-d]*c)>=DEPTH)

            b[i+]+=b[i]/DEPTH,b[i]%=DEPTH ;

    for(;b[b[]+];b[]++,b[b[]+]=b[b[]]/DEPTH,b[b[]]%=DEPTH);

    for(;!b[b[]]&&b[]>;b[]--);

}

/**************************************************************************/

/* 大数相除,读入被除数a，除数b，结果保存在c[]数组                         */

/* 需要comp()函数                                                         */

/**************************************************************************/

void div(bignum_t c,bignum_t a,const bignum_t b)

{

    int h,l,m,i ;

    memset((void*)c,,sizeof(bignum_t));

    c[]=(b[]<a[]+)?(a[]-b[]+): ;

    for(i=c[];i;sub(a,b,c[i]=m,i-),i--)

        for(h=DEPTH-,l=,m=(h+l+)>>;h>l;m=(h+l+)>>)

            if(comp(b,m,i-,a))h=m- ;

            else l=m ;

    for(;!c[c[]]&&c[]>;c[]--);

    c[]=c[]>?c[]: ;

}

void div(bignum_t a,const int b,int&c)

{

    int i ;

    for(c=,i=a[];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);

    for(;!a[a[]]&&a[]>;a[]--);

}

/************************************************************************/

/* 大数平方根，读入大数a，结果保存在b[]数组里                           */

/* 需要comp()函数                                                       */

/************************************************************************/

void sqrt(bignum_t b,bignum_t a)

{

    int h,l,m,i ;

    memset((void*)b,,sizeof(bignum_t));

    for(i=b[]=(a[]+)>>;i;sub(a,b,m,i-),b[i]+=m,i--)

        for(h=DEPTH-,l=,b[i]=m=(h+l+)>>;h>l;b[i]=m=(h+l+)>>)

            if(comp(b,m,i-,a))h=m- ;

            else l=m ;

    for(;!b[b[]]&&b[]>;b[]--);

    for(i=;i<=b[];b[i++]>>=);

}

/************************************************************************/

/* 返回大数的长度                                                       */

/************************************************************************/

int length(const bignum_t a)

{

    int t,ret ;

    for(ret=(a[]-)*DIGIT,t=a[a[]];t;t/=,ret++);

    return ret>?ret: ;

}

/************************************************************************/

/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数               */

/************************************************************************/

int digit(const bignum_t a,const int b)

{

    int i,ret ;

    for(ret=a[(b-)/DIGIT+],i=(b-)%DIGIT;i;ret/=,i--);

    return ret% ;

}

/************************************************************************/

/* 返回大数末尾0的个数                                                  */

/************************************************************************/

int zeronum(const bignum_t a)

{

    int ret,t ;

    for(ret=;!a[ret+];ret++);

    for(t=a[ret+],ret*=DIGIT;!(t%);t/=,ret++);

    return ret ;

}

void comp(int*a,const int l,const int h,const int d)

{

    int i,j,t ;

    for(i=l;i<=h;i++)

        for(t=i,j=;t>;j++)

            while(!(t%j))

                a[j]+=d,t/=j ;

}

void convert(int*a,const int h,bignum_t b)

{

    int i,j,t= ;

    memset(b,,sizeof(bignum_t));

    for(b[]=b[]=,i=;i<=h;i++)

        if(a[i])

            for(j=a[i];j;t*=i,j--)

                if(t*i>DEPTH)

                    mul(b,t),t= ;

    mul(b,t);

}

/************************************************************************/

/* 组合数                                                               */

/************************************************************************/

void combination(bignum_t a,int m,int n)

{

    int*t=new int[m+];

    memset((void*)t,,sizeof(int)*(m+));

    comp(t,n+,m,);

    comp(t,,m-n,-);

    convert(t,m,a);

    delete[]t ;

}

/************************************************************************/

/* 排列数                                                               */

/************************************************************************/

void permutation(bignum_t a,int m,int n)

{

    int i,t= ;

    memset(a,,sizeof(bignum_t));

    a[]=a[]= ;

    for(i=m-n+;i<=m;t*=i++)

        if(t*i>DEPTH)

            mul(a,t),t= ;

    mul(a,t);

}

#define SGN(x) ((x)>0?1:((x)<0?-1:0))

#define ABS(x) ((x)>0?(x):-(x))

int read(bignum_t a,int&sgn,istream&is=cin)

{

    char str[MAX*DIGIT+],ch,*buf ;

    int i,j ;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>str))return  ;

    buf=str,sgn= ;

    if(*buf=='-')sgn=-,buf++;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

        ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

        for(a[i]=,j=;j<DIGIT;j++)

            a[i]=a[i]*+buf[i*DIGIT--j]-'' ;

    for(;!a[a[]]&&a[]>;a[]--);

    if(a[]==&&!a[])sgn= ;

    return  ;

}

struct bignum

{

    bignum_t num ;

    int sgn ;

    public :

    inline bignum()

    {

        memset(num,,sizeof(bignum_t));

        num[]= ;

        sgn= ;

    }

    inline int operator!()

    {

        return num[]==&&!num[];

    }

    inline bignum&operator=(const bignum&a)

    {

        memcpy(num,a.num,sizeof(bignum_t));

        sgn=a.sgn ;

        return*this ;

    }

    inline bignum&operator=(const int a)

    {

        memset(num,,sizeof(bignum_t));

        num[]= ;

        sgn=SGN (a);

        add(num,sgn*a);

        return*this ;

    }

    ;

    inline bignum&operator+=(const bignum&a)

    {

        if(sgn==a.sgn)add(num,a.num);

        else if

            (sgn&&a.sgn)

        {

            int ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub (num,t);

                sgn=a.sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if(!sgn)

            memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;

        return*this ;

    }

    inline bignum&operator+=(const int a)

    {

        if(sgn*a>)add(num,ABS(a));

        else if(sgn&&a)

        {

            int  ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]= ;

                add(num,ABS (a));

                sgn=-sgn ;

                sub(num,t);

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if

            (!sgn)sgn=SGN(a),add(num,ABS(a));

        return*this ;

    }

    inline bignum operator+(const bignum&a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        ret.sgn=sgn ;

        ret+=a ;

        return ret ;

    }

    inline bignum operator+(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        ret.sgn=sgn ;

        ret+=a ;

        return ret ;

    }

    inline bignum&operator-=(const bignum&a)

    {

        if(sgn*a.sgn<)add(num,a.num);

        else if

            (sgn&&a.sgn)

        {

            int ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub(num,t);

                sgn=-sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if(!sgn)add (num,a.num),sgn=-a.sgn ;

        return*this ;

    }

    inline bignum&operator-=(const int a)

    {

        if(sgn*a<)add(num,ABS(a));

        else if(sgn&&a)

        {

            int  ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t ;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]= ;

                add(num,ABS(a));

                sub(num,t);

                sgn=-sgn ;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if

            (!sgn)sgn=-SGN(a),add(num,ABS(a));

        return*this ;

    }

    inline bignum operator-(const bignum&a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn ;

        ret-=a ;

        return ret ;

    }

    inline bignum operator-(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn ;

        ret-=a ;

        return ret ;

    }

    inline bignum&operator*=(const bignum&a)

    {

        bignum_t t ;

        mul(t,num,a.num);

        memcpy(num,t,sizeof(bignum_t));

        sgn*=a.sgn ;

        return*this ;

    }

    inline bignum&operator*=(const int a)

    {

        mul(num,ABS(a));

        sgn*=SGN(a);

        return*this ;

    }

    inline bignum operator*(const bignum&a)

    {

        bignum ret ;

        mul(ret.num,num,a.num);

        ret.sgn=sgn*a.sgn ;

        return ret ;

    }

    inline bignum operator*(const int a)

    {

        bignum ret ;

        memcpy(ret.num,num,sizeof (bignum_t));

        mul(ret.num,ABS(a));

        ret.sgn=sgn*SGN(a);

        return ret ;

    }

    inline bignum&operator/=(const bignum&a)

    {

        bignum_t t ;

        div(t,num,a.num);

        memcpy (num,t,sizeof(bignum_t));

        sgn=(num[]==&&!num[])?:sgn*a.sgn ;

        return*this ;

    }

    inline bignum&operator/=(const int a)

    {

        int t ;

        div(num,ABS(a),t);

        sgn=(num[]==&&!num [])?:sgn*SGN(a);

        return*this ;

    }

    inline bignum operator/(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(t,num,sizeof(bignum_t));

        div(ret.num,t,a.num);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*a.sgn ;

        return ret ;

    }

    inline bignum operator/(const int a)

    {

        bignum ret ;

        int t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*SGN(a);

        return ret ;

    }

    inline bignum&operator%=(const bignum&a)

    {

        bignum_t t ;

        div(t,num,a.num);

        if(num[]==&&!num[])sgn= ;

        return*this ;

    }

    inline int operator%=(const int a)

    {

        int t ;

        div(num,ABS(a),t);

        memset(num,,sizeof (bignum_t));

        num[]= ;

        add(num,t);

        return t ;

    }

    inline bignum operator%(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(t,ret.num,a.num);

        ret.sgn=(ret.num[]==&&!ret.num [])?:sgn ;

        return ret ;

    }

    inline int operator%(const int a)

    {

        bignum ret ;

        int t ;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        memset(ret.num,,sizeof(bignum_t));

        ret.num[]= ;

        add(ret.num,t);

        return t ;

    }

    inline bignum&operator++()

    {

        *this+= ;

        return*this ;

    }

    inline bignum&operator--()

    {

        *this-= ;

        return*this ;

    }

    ;

    inline int operator>(const bignum&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>:):(sgn<?(a.sgn<?comp(num,a.num)<:):a.sgn<);

    }

    inline int operator>(const int a)

    {

        return sgn>?(a>?comp(num,a)>:):(sgn<?(a<?comp(num,-a)<:):a<);

    }

    inline int operator>=(const bignum&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>=:):(sgn<?(a.sgn<?comp(num,a.num)<=:):a.sgn<=);

    }

    inline int operator>=(const int a)

    {

        return sgn>?(a>?comp(num,a)>=:):(sgn<?(a<?comp(num,-a)<=:):a<=);

    }

    inline int operator<(const bignum&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>:):(sgn>?(a.sgn>?comp(num,a.num)<:):a.sgn>);

    }

    inline int operator<(const int a)

    {

        return sgn<?(a<?comp(num,-a)>:):(sgn>?(a>?comp(num,a)<:):a>);

    }

    inline int operator<=(const bignum&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>=:):(sgn>?(a.sgn>?comp(num,a.num)<=:):a.sgn>=);

    }

    inline int operator<=(const int a)

    {

        return sgn<?(a<?comp(num,-a)>=:):

        (sgn>?(a>?comp(num,a)<=:):a>=);

    }

    inline int operator==(const bignum&a)

    {

        return(sgn==a.sgn)?!comp(num,a.num): ;

    }

    inline int operator==(const int a)

    {

        return(sgn*a>=)?!comp(num,ABS(a)): ;

    }

    inline int operator!=(const bignum&a)

    {

        return(sgn==a.sgn)?comp(num,a.num): ;

    }

    inline int operator!=(const int a)

    {

        return(sgn*a>=)?comp(num,ABS(a)): ;

    }

    inline int operator[](const int a)

    {

        return digit(num,a);

    }

    friend inline istream&operator>>(istream&is,bignum&a)

    {

        read(a.num,a.sgn,is);

        return  is ;

    }

    friend inline ostream&operator<<(ostream&os,const bignum&a)

    {

        if(a.sgn<)

            os<<'-' ;

        write(a.num,os);

        return os ;

    }

    friend inline bignum sqrt(const bignum&a)

    {

        bignum ret ;

        bignum_t t ;

        memcpy(t,a.num,sizeof(bignum_t));

        sqrt(ret.num,t);

        ret.sgn=ret.num[]!=||ret.num[];

        return ret ;

    }

    friend inline bignum sqrt(const bignum&a,bignum&b)

    {

        bignum ret ;

        memcpy(b.num,a.num,sizeof(bignum_t));

        sqrt(ret.num,b.num);

        ret.sgn=ret.num[]!=||ret.num[];

        b.sgn=b.num[]!=||ret.num[];

        return ret ;

    }

    inline int length()

    {

        return :: length(num);

    }

    inline int zeronum()

    {

        return :: zeronum(num);

    }

    inline bignum C(const int m,const int n)

    {

        combination(num,m,n);

        sgn= ;

        return*this ;

    }

    inline bignum P(const int m,const int n)

    {

        permutation(num,m,n);

        sgn= ;

        return*this ;

    }

};

/*

int main()

{

    bignum a,b,c;

    cin>>a>>b;

    cout<<"加法:"<<a+b<<endl;

    cout<<"减法:"<<a-b<<endl;

    cout<<"乘法:"<<a*b<<endl;

    cout<<"除法:"<<a/b<<endl;

    c=sqrt(a);

    cout<<"平方根:"<<c<<endl;

    cout<<"a的长度:"<<a.length()<<endl;

    cout<<"a的末尾0个数:"<<a.zeronum()<<endl<<endl;

    cout<<"组合: 从10个不同元素取3个元素组合的所有可能性为"<<c.C(10,3)<<endl;

    cout<<"排列: 从10个不同元素取3个元素排列的所有可能性为"<<c.P(10,3)<<endl;

    return 0 ;

}

*/

int g[];

bignum dp[][];

int main()

{

    int n,k;

    while(cin>>n>>k)

    {

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;i++)

            scanf("%d",g+i);

        for(int i=;i<=n;i++)

            dp[i][]=;

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=k;j++)

            {

                for(int p=;p<i;p++)

                {

                    if(g[p] < g[i])

                    {

                        dp[i][j] += dp[p][j-];

                    }

                }

            }

        }

        bignum sum;

        sum=;

        for(int i=;i<=n;i++)

            sum += dp[i][k];

        cout<<sum<<endl;

    }

    return ;

}

也是一个简单的dp.

令dp[i][j]表示当前走到第i,j个位置的最小贡献，我们可以假定(i+j)为奇数，由该状态可以转移向最多4个位置，就可以了。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define INF 1000000000

int dp[][];

int g[][];

int main()

{

    int n,m;

    while(cin>>n>>m)

    {

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                scanf("%d",&g[i][j]);

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                dp[i][j]=INF;

        dp[][]=;

        for(int i=;i<=n;i++)

        {

            for(int j=-(i%)+;j<=m;j+=)

            {

                if(i+<=n) dp[i+][j]=min(dp[i+][j],dp[i][j]+g[i][j]*g[i+][j]);

                if(j+<=m) dp[i][j+]=min(dp[i][j+],dp[i][j]+g[i][j]*g[i][j+]);

                if(i+<=n&&j+<=m) dp[i+][j+]=min( dp[i+][j+],dp[i][j]+min(g[i][j]*g[i+][j],g[i][j]*g[i][j+]) );

            }

        }

        int ans=INF;

        if(n!=) ans=min(ans,dp[n-][m]+g[n-][m]*g[n][m]);

        if(m!=) ans=min(ans,dp[n][m-]+g[n][m-]*g[n][m]);

        cout<<ans<<endl;

    }

    return ;

}

d.比赛的时候没有想出来。就是个概率题，当年考研的时候概率果真还是没有复习好。

我们先假设有n个独立事件，a1,a2,a3,...,an。对应发生的概率为p1,p2,p3,...,pn

则最后有多少个事件发生的期望为 x = p1+p2+p3+...+pn

而最后有多少个事件数平方的期望为 x^2=(p1+p2+p3+...pn)^2 + [(p1-p1^2)+(p2-p2^2)+(p3-p3^2)+...+(p3-p3^2)] (其实就是任意两个事件同时发生的概率和)

为什么呢？我是举了几个例子用归纳法证明的。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <algorithm>

using namespace std;

int g[][];

double p[][];

int main()

{

    int n,m;

    while(cin>>n>>m)

    {

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                scanf("%d",&g[i][j]);

        for(int i=;i<=n;i++)

        {

            double sum=;

            for(int j=;j<=m;j++)

            {

                sum += g[i][j];

            }

            for(int j=;j<=m;j++)

            {

                p[i][j] = (double)g[i][j]/sum;

            }

        }

        double ans=;

        for(int j=;j<=m;j++)

        {

            double sum=;

            double tmp1=;

            for(int i=;i<=n;i++)

            {

                sum += p[i][j];

                tmp1 += p[i][j]-p[i][j]*p[i][j];

            }

            ans += sum*sum+tmp1;

        }

        printf("%.2lf\n",ans);

    }

    return ;

}

巴特西

BestCoder Round #63 (div.2)

最新文章

热门文章