Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Oh shit !,确实精度问题,换成long double 就AC

Posted by 0801050332 at 2010-07-22 09:24:42 on Problem 1191
>请问各位,到底是哪里的运算提高了对精度的要求???
>下面是我的源程序:
>严格翻版黑书上的思想^^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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator