| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:拜托哪个善良的牛人帮我看一下,为什么那个s数组求得不对啊!?明明这个道理很对啊!aUb=a+b-a^b啊In Reply To:拜托哪个善良的牛人帮我看一下,为什么那个s数组求得不对啊!?明明这个道理很对啊!aUb=a+b-a^b啊 Posted by:snowshine09 at 2011-08-05 19:18:54 > #include<cstdio>
> #include<cstdlib>
> #include<cmath>
> #include<string>
>
> int d[16][9][9][9][9],s[9][9][9][9],mtr[9][9],ss[9][9];
>
> int MIN(int a ,int b)
> {
> if(a<b)return a;
> else return b;
> }
> int main()
> {
> int i,n,k,j,a,temp=0,sum=0,x1,x2,y1,y2;
> double ave,tot=0;
> scanf("%d",&n);
> for(i=0;i<8;++i)
> {
> for(j=0;j<8;++j)
> {
> scanf("%d",&mtr[i][j]);
> sum+=mtr[i][j];
> tot+=mtr[i][j];
> if(!i)ss[i][j]=sum;
> else ss[i][j]=ss[i-1][j]+sum;
> if(j==7)sum=0;
> }
> }
> ave=tot/n;
> for(x1=0;x1<8;++x1)
> for(y1=0;y1<8;++y1)
> for(x2=x1;x2<8;++x2)
> for(y2=y1;y2<8;++y2)
> {
> if(x1==0||y1==0)temp=ss[x2][y2];
> else
> temp=ss[x2][y2]+ss[x1-1][y1-1]-ss[x1-1][y2]-ss[x2][y1-1];
> s[x1][y1][x2][y2]=temp*temp;
> d[0][x1][y1][x2][y2]=s[x1][y1][x2][y2];
> }
> /* for (x1=0; x1<8; x1++)
> {
> for (y1=0; y1<8; y1++)
> {
> for (x2=x1; x2<8; x2++)
> {
> sum = 0;
> for (y2=y1; y2<8; y2++)
> {
> sum += mtr[x2][y2];
> if (x2 == x1)
> {
> s[x1][y1][x2][y2] = sum;
> }
> else
> {
> s[x1][y1][x2][y2] = s[x1][y1][x2-1][y2] + sum;
> }
> s[x1][y1][x2][y2] *= s[x1][y1][x2][y2];
> d[0][x1][y1][x2][y2] = s[x1][y1][x2][y2] ;
> }
> }
> }
> } */
> for(k=1;k<=n;++k)
> for(x1=0;x1<8;++x1)
> for(y1=0;y1<8;++y1)
> for(x2=x1;x2<8;++x2)
> for(y2=y1;y2<8;++y2)
> {
> d[k][x1][y1][x2][y2]=2000000000;
> for(i=x1;i<x2;++i)//横切
> {
> d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][y1][i][y2]+s[i+1][y1][x2][y2]);
> d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][i+1][y1][x2][y2]+s[x1][y1][i][y2]);
> }
> for(i=y1;i<y2;++i)//竖切
> {
> d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][y1][x2][i]+s[x1][i+1][x2][y2]);
> d[k][x1][y1][x2][y2]=MIN(d[k][x1][y1][x2][y2],d[k-1][x1][i+1][x2][y2]+s[x1][y1][x2][i]);
> }
> }
>
> /*for (k=1; k<=n-1; k++)
> {
> for (x1=0; x1<8; x1++)
> {
> for (y1=0; y1<8; y1++)
> {
> for (x2=x1; x2<8; x2++)
> {
> for (y2=y1; y2<8; y2++)
> {
> d[k][x1][y1][x2][y2] = 2000000000;
> for (a=x1; a<x2; a++)
> {
> temp = MIN(d[k-1][x1][y1][a][y2] + s[a+1][y1][x2][y2],
> d[k-1][a+1][y1][x2][y2] + s[x1][y1][a][y2]);
> d[k][x1][y1][x2][y2] = MIN(d[k][x1][y1][x2][y2], temp);
> }
>
> for (a=y1; a<y2; a++)
> {
> temp = MIN(d[k-1][x1][y1][x2][a] + s[x1][a+1][x2][y2],
> d[k-1][x1][a+1][x2][y2] + s[x1][y1][x2][a] );
> d[k][x1][y1][x2][y2] = MIN(d[k][x1][y1][x2][y2], temp);
> }
> }
> }
> }
> }
> }
> */
> double ret = sqrt((double)d[n-1][0][0][7][7]/(double)n-ave*ave);
> printf("%.3f\n",ret);
> return 0;
> }
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator