| ||||||||||
| 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 | |||||||||
Oh shit !,确实精度问题,换成long double 就AC>请问各位,到底是哪里的运算提高了对精度的要求???
>下面是我的源程序:
>严格翻版黑书上的思想^^DP
>#include <iostream>
#include <iomanip>
#include <cmath>
//#include <fstream>
using namespace std;
long double record[8][8][8][8][15];
int chessBoard[8][8];
void DP(long double rec[][8][8][8][15],int board[][8],int split)
{
long double temp;
//无分割
for (int i=0;i<8;i++)
for(int j=0;j<8;j++)
for(int k=i;k<8;k++)
{
for(int l=j;l<8;l++)
{
for (int m=i;m<=k;m++)
for (int n=j;n<=l;n++)
{
rec[i][j][k][l][0]+=(long double)board[m][n];
}
rec[i][j][k][l][0]*=rec[i][j][k][l][0];
//cout<<rec[i][j][k][l][0]<<' ';
}
//cout<<endl;
//system("pause");
}
//进行一次分割
if(split>2)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
for(int k=i;k<8;k++)
for(int l=j;l<8;l++)
{
rec[i][j][k][l][1]=40961000;
for (int m=j;m<l;m++)
{
if(rec[i][j][k][l][1]>(temp=rec[i][j][k][m][0]+rec[i][m+1][k][l][0]))
rec[i][j][k][l][1]=temp;
//if(rec[i][j][k][l][1]>(temp=rec[i][j][k][m][sp-1]+rec[i][m][k][l][0]))
//rec[i][j][k][l][1]=temp;
}
for (int m=i;m<k;m++)
{
if(rec[i][j][k][l][1]>(temp=rec[i][j][m][l][0]+rec[m+1][j][k][l][0]))
rec[i][j][k][l][1]=temp;
//if(rec[i][j][k][l][1]>(temp=rec[i][j][m][l][sp-1]+rec[m][j][k][l][0]))
// rec[i][j][k][l][1]=temp;
}
}
}
for (int sp=2;sp<split-1;sp++)
{
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)
for(int k=i;k<8;k++)
for(int l=j;l<8;l++)
{
rec[i][j][k][l][sp]=40961000;
for (int m=j;m<l;m++)
{
if(rec[i][j][k][l][sp]>(temp=rec[i][j][k][m][0]+rec[i][m+1][k][l][sp-1]))
rec[i][j][k][l][sp]=temp;
if(rec[i][j][k][l][sp]>(temp=rec[i][j][k][m][sp-1]+rec[i][m+1][k][l][0]))
rec[i][j][k][l][sp]=temp;
}
for (int m=i;m<k;m++)
{
if(rec[i][j][k][l][sp]>(temp=rec[i][j][m][l][0]+rec[m+1][j][k][l][sp-1]))
rec[i][j][k][l][sp]=temp;
if(rec[i][j][k][l][sp]>(temp=rec[i][j][m][l][sp-1]+rec[m+1][j][k][l][0]))
rec[i][j][k][l][sp]=temp;
}
}
}
//分割split-1次,只对整个棋盘分割
rec[0][0][7][7][split-1]=40961000;
for (int m=0;m<8;m++)
{
if(rec[0][0][7][7][split-1]>(temp=rec[0][0][7][m][0]+rec[0][m+1][7][7][split-2]))
rec[0][0][7][7][split-1]=temp;
if(rec[0][0][7][7][split-1]>(temp=rec[0][0][7][m][split-2]+rec[0][m+1][7][7][0]))
rec[0][0][7][7][split-1]=temp;
}
for (int m=0;m<7;m++)
{
if(rec[0][0][7][7][split-1]>(temp=rec[0][0][m][7][0]+rec[m+1][0][7][7][split-2]))
rec[0][0][7][7][split-1]=temp;
if(rec[0][0][7][7][split-1]>(temp=rec[0][0][m][7][split-2]+rec[m+1][0][7][7][0]))
rec[0][0][7][7][split-1]=temp;
}
}
int main()
{
//ifstream in("input.txt");
int nSplit;
long double nAve=0;
cin>>nSplit;
for (int i=0;i<8;i++)
{
for (int j=0;j<8;j++)
{
cin>>chessBoard[i][j];
nAve+=(long double )chessBoard[i][j];
}
}
nAve/=nSplit;
//cout<<nAve<<endl;
//cout<<nAve<<endl;
DP(record,chessBoard,nSplit);
//cout<<record[0][0][7][3][0]<<endl;
//cout<<record[0][0][7][7][nSplit-1]<<endl;
//cout<<static_cast<float>(record[0][0][7][7][nSplit-1])/nSplit<<endl;
double nResult=sqrt(record[0][0][7][7][nSplit-1]/nSplit-nAve*nAve);
cout.setf(ios::fixed);
cout<<setprecision(3)<<nResult<<endl;
//system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator