題干：

Frog fell into a maze. This maze is a rectangle containing?NN?rows and?MM?columns. Each grid in this maze contains a number, which is called the magic value. Frog now stays at grid (1, 1), and he wants to go to grid (N, M). For each step, he can go to either the grid right to his current location or the grid below his location. Formally, he can move from grid (x, y) to (x + 1, y) or (x, y +1), if the grid he wants to go exists.?
Frog is a perfectionist, so he'd like to find the most beautiful path. He defines the beauty of a path in the following way. Let’s denote the magic values along a path from (1, 1) to (n, m) as?A1,A2,…AN+M?1A1,A2,…AN+M?1, and?AavgAavg?is the average value of all?AiAi. The beauty of the path is?(N+M–1)(N+M–1)?multiplies the variance of the values:(N+M?1)∑N+M?1i=1(Ai?Aavg)2(N+M?1)∑i=1N+M?1(Ai?Aavg)2?
In Frog's opinion, the smaller, the better. A path with smaller beauty value is more beautiful. He asks you to help him find the most beautiful path.?

Input

The first line of input contains a number?TT?indicating the number of test cases (T≤50T≤50).?
Each test case starts with a line containing two integers?NN?and?MM?(1≤N,M≤301≤N,M≤30). Each of the next?NN?lines contains?MM?non-negative integers, indicating the magic values. The magic values are no greater than 30.?

Output

For each test case, output a single line consisting of “Case #X: Y”.?XX?is the test case number starting from 1.?YY?is the minimum beauty value.

Sample Input

1 2 2 1 2 3 4

Sample Output

Case #1: 14

題目大意：

在一個N*M的數字方格中，尋找一條從左上角(1,1)到右下角(n,m)的路徑，每次只能往右走或往下走。

使得路徑上的數字方差（或者說這個式子）最小。（n,m,a[i][j]均<=30）

解題報告：

如果說是方差的話更加不好思考，還是直接看上面這個式子，不難化簡出：原式。

然后本來想直接貪心這個式子最小的情況下轉移，但是無法證明正確性。

其實我們不妨多一維狀態，記錄dp[i][j][k]代表從(1,1)走到(i,j)且路徑的和為k的最小平方和。因為要求式子的值最小，所以在原式路徑和相同的情況下被減數越小越好，又因為(i,j)不論從哪里轉移過來，此時的(n+m-1)肯定為(i+j-1)，是個定值，所以只需要維護平方和最小值即可。注意初始化狀態的時候不是dp[0][0][0]了。。通過畫二維矩陣就容易看出初始化的狀態是哪些。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 55 + 5; ll a[MAX][MAX]; ll dp[55][55][2222]; int n,m; int main() {int T,iCase=0;cin>>T;while(T--) {scanf("%d%d",&n,&m);int sum = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {scanf("%lld",&a[i][j]);sum += a[i][j];}}for(int i = 0; i<=n; i++) {for(int j = 0; j<=m; j++) for(int k = 0; k<=2000; k++) dp[i][j][k] = 1e12;}dp[0][1][0]=dp[1][0][0]=0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {for(int k = a[i][j]; k<=2000; k++) {dp[i][j][k] = min(dp[i-1][j][k-a[i][j]]+a[i][j]*a[i][j],dp[i][j-1][k-a[i][j]]+a[i][j]*a[i][j]);}} }ll ans = 0x3f3f3f3f;for(int i = 0; i<=2000; i++) {ans = min(1LL*ans,(n+m-1)*dp[n][m][i]-i*i);}printf("Case #%d: %lld\n",++iCase,ans);}return 0 ; } /* 1 2 2 1 2 3 4 */

?

總結

以上是生活随笔為你收集整理的【HDU - 5492】Find a path（dp，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。