hdu5492

末蓝、 2024-04-20 10:25 70阅读 0赞

##  ##

hdu5492

> 陈大哥的毒瘤题T1

### 题意： ###

> 差不多就是根据题意推式子，求最小方差。

### 解法： ###

> 首先，可以观察到，如果我们直接暴力去取平均数，很大概率会取出来小数，所以一个很直观的想法就是把平均数从式子里消去，让小数对结果不产生影响。  
> 首先我们知道 $ ans = (n+m-1) \\sum\_\{i=1\}^\{n+m-1\} (A\_i - A\_\{avg\}) ^ 2 $ ，根据数学知识可知 $ ans = \\sum\_\{i=1\}^\{n+m-1\} (A\_i^2 - 2 \\times A\_\{avg\} \\times A\_i + A\_\{avg\}^2) $ ， 将式子拆分后得 $ ans = (n+m-1)(A\_1^2 + \\cdots + A\_\{n+m-1\}^2 ) + 2A\_\{avg\}(n+m-1)(A\_1 + \\cdots + A\_\{n+m-1\}) + (n + m - 1)^2 A\_\{avg\}^2 $  
> 令 $ sum = A\_1 + \\cdots + A\_\{n+m-1\} = \\sum\_\{i = 1\}^\{n+m-1\} A\_i $ , 又因为 $ A\_\{avg\} = \\frac\{\\sum\_\{i=1\}^\{n+m-1\}\}\{n+m-1\} = \\frac\{sum\}\{n+m-1\} $  
> 所以原式可化为 $ ans = (n+m-1)\\sum\_\{i=1\}^\{n-m+1\} A\_i^2 - sum $  
> 所以现在我们只需要求出对一个给定的sum，求出最小的 $ \\sum\_\{i=1\}^\{n+m-1\}A\_i^2 $ 即可。  
> 所以定义状态 $ f\[i\]\[j\]\[k\] $ 表示走到 $ (i,j) $ 时，总和为k的最小代价  
> 答案就是 $ (n+m-1)f\[i\]\[j\]\[k\] - k^2 $ 的最小值。

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define LL long long int a[40][40],m,n,T; int dp[40][40][2000],rk; inline void open_judge() { freopen("path.in","r",stdin); freopen("path.out","w",stdout); } int main() { scanf("%d",&T); while(T--) { rk++; scanf("%d%d",&n,&m); for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { scanf("%d",&a[i][j]); } } for(int i = 0 ; i <= n ; i++) { for(int j = 0 ; j <= m ; j++) { for(int k = 0 ; k <= 1800 ; k++) { dp[i][j][k] = 1e8; } } } dp[1][1][a[1][1]] = a[1][1] * a[1][1]; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) { if(i == 1 && j == 1) continue; for(int k = a[i][j] ; k <= 1800 ; k++) dp[i][j][k] = min(dp[i - 1][j][k - a[i][j]],dp[i][j - 1][k - a[i][j]]) + a[i][j] * a[i][j]; } } LL ans = 2147483647; for(int k = 0 ; k <= 1800 ; k++) { LL tmp = 1ll * (n + m - 1) * dp[n][m][k] - k * k; if(ans > tmp) ans = tmp; } printf("Case #%d: %d\n",rk,ans); } //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11385769.html