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

Re:WA的可以看一下

Posted by NaN3 at 2013-05-26 16:31:56 on Problem 1191
In Reply To:WA的可以看一下 Posted by:allh123 at 2013-05-05 15:48:33
> 用double,然后用%.3lfWA
> 用%.3fAC
> 在DP时min的初始值赋为10^7WA
> 赋为10^8AC
> 这点我还比较想得通,棋盘最大的总分和为6400,最大的平方和即为6400^6400,为40960000
> 你赋的min值至少应该大于这个数,否则就不对了,所以10^7可能会错
> 我中间赋过一个0x7fffffff,既然导致出现了负数,怎么会啊。。。。。不了解

表示那个1e7 不是问题呀
我的代码试了试没错的说...可能是你的代码里面别的地方出错了吧...

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,l,n) for(int i = l; i <= n; i++)
#define MIN 1e8

using namespace std;

namespace Solve{
	int N; int Plant[8][8];
	int d[16][8][8][8][8], s[8][8][8][8];

	void init(){ 
		cin>>N; rep(i,8) rep(j,8) cin>>Plant[i][j]; 
		memset(d,-1,sizeof(d)); memset(s, -1, sizeof(s));
	}

	double getSumMatrix(int x1, int x2, int y1, int y2){
		int &S = s[x1][y1][x2][y2];
		if( S != -1) { return S;}
		else{
			double sum = 0;
			REP(a,x1,x2) REP(b,y1,y2) sum += Plant[a][b];
			S = pow(sum,2); return S;
		}
	}

	double getMinMatrix(int k,int x1, int x2, int y1, int y2){
		int &D = d[k][x1][y1][x2][y2]; 
		if( D != -1 ) return D;
		else if( k == N - 1 ) return getSumMatrix(x1,x2,y1,y2);
		else {
			double MinAns = MIN; double colcut = MIN,rowcut = MIN;
			for(int a = x1; a < x2; a ++){
				double leftcut = getMinMatrix(k+1,a+1,x2,y1,y2) + getSumMatrix(x1,a,y1,y2);
				double rightcut = getMinMatrix(k+1,x1,a,y1,y2) + getSumMatrix(a+1,x2,y1,y2);
				double tcolcut = (leftcut < rightcut) ? leftcut : rightcut;
				if(tcolcut < colcut) colcut = tcolcut;
			}
			for(int b = y1; b < y2; b ++){
				double upcut = getMinMatrix(k+1,x1,x2,b+1,y2) + getSumMatrix(x1,x2,y1,b);
				double downcut = getMinMatrix(k+1,x1,x2,y1,b) + getSumMatrix(x1,x2,b+1,y2);
				double trowcut = (upcut < downcut) ? upcut : downcut;
				if(trowcut < rowcut) rowcut = trowcut;
			}
			MinAns = (colcut < rowcut) ? colcut : rowcut;
			D = MinAns;
			return D;
		}
	}

	void solve(){
		init();
		int x1 = 0, x2 = 7, y1 = 0, y2 = 7;
		double ans = getMinMatrix(0,x1,x2,y1,y2);
		double sum = 0; rep(x,8) rep(y,8) sum += Plant[x][y];
		double avg = sum / N;

		printf("%.3f", sqrt(ans/N - pow(avg,2)));
	}

}

int main(){
	Solve::solve();
	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