hdu5492-蒲公英云

hdu5492

末蓝、 2024-04-20 10:25 128阅读 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; }