| ||||||||||
| 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 | |||||||||
Re:WA的可以看一下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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator