| ||||||||||
| 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