hdu 5492 （暴力+nice）

题意：在矩阵中，找一条路从 （1,1）->（n，m），使方差最小

思路: T = (N+M−1)∑N+M−1i=1(Ai−Aavg)2

将N + M - 1乘进去，即求1 ~ N+M-1，（N + M - 1）*A[i] - (A[i] + ..... + A[N]) 的和由于

假设Aavg可以是任何数，但只有当其是平均值时T才会最小（感觉别人都好厉害 /(ㄒoㄒ)/~~）

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <time.h>

#include <algorithm>

typedef long long ll;

using namespace std;

int a[35][35],f[35][35];

int n,m;

int fin(int x)

{

    int N = n+m-1;

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++)

        {

            if(i == 1 && j == 1)

                f[i][j] = (N*a[i][j]-x)*(N*a[i][j] - x);

            else if(i == 1)

                f[i][j] = f[i][j-1] + (N*a[i][j]-x)*(N*a[i][j] - x);

            else if(j == 1)

                f[i][j] = f[i-1][j] + (N*a[i][j]-x)*(N*a[i][j] - x);

            else

                f[i][j] = min(f[i-1][j],f[i][j-1]) + (N*a[i][j]-x)*(N*a[i][j] - x);

        }

        return f[n][m]/N;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int i = 1; i <= T; i++)

    {

        scanf("%d%d",&n,&m);

        for(int k = 1; k <= n; k++)

            for(int j = 1; j <= m; j++)

            {

                scanf("%d",&a[k][j]);

            }

        int ans = 10000000;

        for(int k = 1; k <= 2000; k++)

        {

            ans = min(ans,fin(k));

        }

        printf("Case #%d: %d\n",i,ans);

    }

}

　　

ps.我们需要的仅仅是不停找借口让自己坚持下去