| ||||||||||
| 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 | |||||||||
水dp,0ms一次AC,附代妈#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
int MAX = 2147483647;
int MIN(int a, int b){
if(a > b) return b;
return a;
}
int main() {
int N;
int val[8][8];
cin >> N;
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
cin >> val[i][j];
val[i][j] *= N;
}
}
int res[16][8][8][8][8] = {0};//res[n][i][j][k][l]: 分成n个,从(i,j)开始,到(k,l)结束
//必须满足:i<=k, j<=l, k+l-i-j>=n-1
//要求的是res[N][0][0][7][7]
//先求sigma
int sigma = 0;
for(int i = 0; i < 8; i++){
for(int j = 0; j < 8; j++){
sigma += val[i][j]/N;
}
}
//初始值:N=1的情况
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++){
int temp = 0;
for(int ii = i; ii <= k; ii++){
for(int jj = j; jj <= l; jj++){
temp += val[ii][jj];
}
}
res[1][i][j][k][l] = (temp-sigma)*(temp-sigma);
}
}
}
}
for(int n = 2; n <= N; n++){
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++){
if(k+l-i-j < n-1) continue;
int temp = MAX;
for(int t = i; t < k; t++){
if(t+l-i-j>=n-2) temp = MIN(temp, res[n-1][i][j][t][l] + res[1][t+1][j][k][l]);
if(k+l-(t+1)-j>=n-2) temp = MIN(temp, res[1][i][j][t][l] + res[n-1][t+1][j][k][l]);
}
for(int t = j; t < l; t++){
if(k+t-i-j>=n-2) temp = MIN(temp, res[n-1][i][j][k][t] + res[1][i][t+1][k][l]);
if(k+l-i-(t+1)>=n-2) temp = MIN(temp, res[1][i][j][k][t] + res[n-1][i][t+1][k][l]);
}
res[n][i][j][k][l] = temp;
}
}
}
}
}
int ans = res[N][0][0][7][7];
double Ans = sqrt(ans * 1.0)/(N*sqrt(N*1.0));
printf("%.3lf\n", Ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator