DP HDOJ 5492 Find a path

我不是女神ヾ 2021-12-23 09:17 134阅读 0赞

**[题目传送门][Link 1]**

**题意：从(1, 1)走到(n, m)，每次往右或往下走，问(N\+M−1)∑(Ai−Aavg)2 的最小值**

**分析：展开式子得到(N\+M−1)∑(Ai2) - (∑(Ai))2的最小值。用普通的搜索要不超时要不爆内存，用dp。注意到和的值很小，最多59\*30，所以dp\[i\]\[j\]\[k\]表示当走到(i, j)点时和为k的最小的平方和，两个方向转移。**

/************************************************
    * Author        :Running_Time
    * Created Time  :2015/9/28 星期一 08:16:33
    * File Name     :I.cpp
     ************************************************/
    
    #include <cstdio>
    #include <algorithm>
    #include <iostream>
    #include <sstream>
    #include <cstring>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <queue>
    #include <deque>
    #include <stack>
    #include <list>
    #include <map>
    #include <set>
    #include <bitset>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    #define lson l, mid, rt << 1
    #define rson mid + 1, r, rt << 1 | 1
    typedef long long ll;
    const int N = 33;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1e9 + 7;
    const double EPS = 1e-8;
    int dp[N][N][N*2*N];
    int a[N][N];
    
    int main(void)    {
        int T, cas = 0;  scanf ("%d", &T);
        while (T--) {
            int n, m;   scanf ("%d%d", &n, &m);
            for (int i=1; i<=n; ++i)    {
                for (int j=1; j<=m; ++j)    {
                    scanf ("%d", &a[i][j]);
                }
            }
            int S = 59 * 30;
            memset (dp, INF, sizeof (dp));
            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)    {
                    for (int k=0; k<=S; ++k)    {
                        int &u = dp[i][j][k];
                        if (u == INF)   continue;
                        if (i + 1 <= n)  {
                            int &v = dp[i+1][j][k+a[i+1][j]];
                            v = min (v, u + a[i+1][j] * a[i+1][j]);
                        }
                        if (j + 1 <= m)  {
                            int &v = dp[i][j+1][k+a[i][j+1]];
                            v = min (v, u + a[i][j+1] * a[i][j+1]);
                        }
                    }
                }
            }
            int ans = INF;
            for (int i=0; i<=S; ++i)    {
                if (dp[n][m][i] == INF) continue;
                ans = min (ans, (n + m - 1) * dp[n][m][i] - i * i);
            }
            printf ("Case #%d: %d\n", ++cas, ans);
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/Running-Time/p/4848935.html

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5492