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 |
好像数据比较水 自己跑14层时间贼长 交上去竟然过了#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator