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

好像数据比较水 自己跑14层时间贼长 交上去竟然过了

Posted by 814264306 at 2019-07-18 15:33:53 on Problem 1191
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int chese[9][9];
int map[9][9];
int n;
float ping;
float ans;
struct Node
{
	int x1, y1;
	int x2, y2;
};
Node node[20];
float nmap[20];
float sum(Node nd) {
	return (float)map[nd.x2][nd.y2] - (float)map[nd.x2][nd.y1] - (float)map[nd.x1][nd.y2] + (float)map[nd.x1][nd.y1];
}
void dfs(Node nds,int t) {
	//横着切
	if (t == n-1) {
		if (nmap[t] > (t == 0 ? 0.0f : nmap[t - 1]) + (sum(nds) - ping)*(sum(nds) - ping))
		{
			nmap[t] =(t == 0 ? 0.0f : nmap[t - 1]) + (sum(nds) - ping)*(sum(nds) - ping);
		}
		return;
	}
	for (int i = nds.x1 + 1; i < nds.x2; i++) {
		Node nds1, nds2;
		//取上面的
		nds1 = nds;
		nds1.x2 = i;
		//取下面的
		nds2 = nds;
		nds2.x1 = i;
		node[t] = nds1;
		nmap[t] = (sum(nds1) - ping)*(sum(nds1) - ping) + (t == 0 ? 0 : nmap[t - 1]);
		if (nmap[t]<nmap[n - 1])
		dfs(nds2, t + 1);
		node[t] = nds2;
		nmap[t] = (sum(nds2) - ping)*(sum(nds2) - ping) + (t == 0 ? 0 : nmap[t - 1]);
		if (nmap[t]<nmap[n - 1])
		dfs(nds1, t + 1);
	}
	for (int i = nds.y1 + 1; i < nds.y2; i++) {
		Node nds1, nds2;
		//取上面的
		nds1 = nds;
		nds1.y2 = i;
		//取下面的
		nds2 = nds;
		nds2.y1 = i;
		node[t] = nds1;
		nmap[t] = (sum(nds1) - ping)*(sum(nds1) - ping) + (t == 0 ? 0.0f : nmap[t - 1]);
		if(nmap[t]<nmap[n-1])
		dfs(nds2, t + 1);
		node[t] = nds2;
		nmap[t] = (sum(nds2) - ping)*(sum(nds2) - ping) + (t == 0 ? 0.0f : nmap[t - 1]);
		if (nmap[t]<nmap[n - 1])
		dfs(nds1, t + 1);
	}
}

int main() {
	cin >> n;
	ans = 99999999.0f;
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			cin >> chese[i][j];
			map[i][j] = 0;
		}
	}
	for (int i = 0; i < 20; i++) {
		nmap[i] = 999999.0f;
	}
	for (int i = 1; i <= 8; i++) {
		for (int j = 1; j <= 8; j++) {
			//i-j
			for (int m = 1; m <= i; m++) {
				for (int n = 1; n <= j; n++) {
					map[i][j] += chese[m][n];
				}
			}
		}
	}

	Node node1;
	ping = (float)map[8][8] / (float)n;
	node1.x1 = node1.y1 = 0;
	node1.x2 = node1.y2 = 8;
	dfs(node1, 0);
	printf("%.3f\n", sqrt(nmap[n-1]/(float)n));
	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