HDU5492 Find a path DP

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5492
各ノードには30以下の重みAがあり、(1,1)点から(n,m)点まで行くには、毎回下または右にしか歩けない.
解析:式展開を簡略化することができる:(n+m-1)*ΣAi^2-(ΣAi)^2,シーケンスとkのときのシーケンスの二乗和の最小値をdp(i,j,k)で表すと,明らかに第1項(すなわちdp(0,0,A[0,0]))はA[0,0]^2であり,下へ行く場合,次の点を歩くとdp(i+1,j,k+A[i+1,j])=dp(i,j,k)+A[i+1,j]^2である.次の点を歩かなければ、dp(i+1,j,k+A[i+1,j])は元の値をそのまま保持し、状態遷移方程式:dp[i+1][j][k+maze[i+1][j]=min(dp[i+1][j][k+maze[i+1][j]]、dp[i][j][k]+maze[i+1][j]*maze[i+1][j]*maze[i+1][j])を得ることができる.
実装コードは次のとおりです.

#include <cstdio>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
int maze[30][30];
int dp[30][30][1800];
int min(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    int t,T=1,m,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
          for(int j=0;j<m;j++)
          scanf("%d",&maze[i][j]);
        memset(dp,INF,sizeof(dp));
        dp[0][0][ maze[0][0] ]=maze[0][0]*maze[0][0];
        for(int i=0;i<n;i++)
          for(int j=0;j<m;j++)
          {
              if(i+1<n)
              {
                  for(int k=0;k<=59*30;k++)
                    if(dp[i][j][k]!=INF)
                      dp[i+1][j][ k+maze[i+1][j] ]=min(dp[i+1][j][ k+maze[i+1][j] ],dp[i][j][k]+maze[i+1][j]*maze[i+1][j]);
              }
              if(j+1<m)
              {
                  for(int k=0;k<=59*30;k++)
                    if(dp[i][j][k]!=INF)
                      dp[i][j+1][ k+maze[i][j+1] ]=min(dp[i][j+1][ k+maze[i][j+1] ],dp[i][j][k]+maze[i][j+1]*maze[i][j+1]);
              }
          }
        int ans=INF;
        for(int i=0;i<=59*30;i++)
          if(dp[n-1][m-1][i]!=INF)
            ans=min(ans,(n+m-1)*dp[n-1][m-1][i]-i*i);
        printf("Case #%d: %d
",T++,ans);
    }
    return 0;
}