# include <cstdio>
# include <cmath>
int n, s[10][10], num[10][10], minsum = 0x7fffffff;
int sum(int x0, int y0, int x1, int y1)
{
    int tem = s[x1][y1]-s[x1][y0]-s[x0][y1]+s[x0][y0];
    return tem*tem;
}
void dfs(int x0, int y0, int x1, int y1, int k, int ss)
{
    if (k == n-1)
    {
        ss += sum(x0,y0,x1,y1);
        if (ss < minsum) minsum = ss;
        return ;
    }

    int tem;
    for(int x = x0+1; x < x1; ++x )
    {
        tem = sum(x0,y0,x,y1);
        if (tem + ss < minsum)
            dfs(x,y0,x1,y1,k+1, ss+tem);

        tem = sum(x,y0,x1,y1);
        if (tem + ss < minsum)
            dfs(x0,y0,x,y1,k+1,ss+tem);
    }

    for(int y = y0+1; y < y1; ++y )
    {
        tem = sum(x0,y0,x1,y);
        if (tem + ss < minsum)
            dfs(x0,y,x1,y1,k+1,ss+tem);

        tem = sum(x0,y,x1,y1);
        if (tem + ss < minsum)
            dfs(x0,y0,x1,y,k+1,ss+tem);
    }
}
int main()
{
   // freopen("1.txt","r",stdin);
    scanf("%d",&n);
    for(int i = 1; i <= 8; ++i)
        for(int j = 1; j <= 8; ++j)
            scanf("%d",&num[i][j]);

    for(int i = 1; i <= 8; ++i)
        for(int j = 1; j <= 8; ++j)
            s[i][j] = s[i][j-1] + num[i][j];
    for(int j = 1; j <= 8; ++j)
        for(int i = 1; i <= 8; ++i)
            s[i][j] += s[i-1][j];

    dfs(0,0,8,8,0,0);
    double ave = s[8][8]*1.0/n;
    printf("%.3lf",sqrt((double)(minsum)/n - ave*ave));
    return 0;
}

• 个人感觉 dp就是搜索吧，只不过加了个记忆化，而且重复的状态不是很多吧 (6) lpl1998 2014-08-19 08:58:43
  • Re:个人感觉 dp就是搜索吧，只不过加了个记忆化，而且重复的状态不是很多吧（扯淡） (35) xlk17875487211 2022-08-22 15:07:06