题意：在矩阵中，找一条路从 （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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            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.我们需要的仅仅是不停找借口让自己坚持下去