HDU5492 Find a path【DP】

本文主要是介绍HDU5492 Find a path【DP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5492

参考博文：http://blog.csdn.net/Baileys0530/article/details/48768123

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define LL __int64
using namespace std;LL A[33][33],dp[33][33][2000];
bool f[33][33][2000];int main()
{int T,kase = 0;LL N,M;scanf("%d",&T);while(T--){scanf("%I64d%I64d",&N,&M);for(LL i = 1; i <= N; ++i){for(LL j = 1; j <= M; ++j){scanf("%I64d",&A[i][j]);}}memset(f,0,sizeof(f));memset(dp,0x3f,sizeof(dp));f[1][1][A[1][1]] = 1;dp[1][1][A[1][1]] = A[1][1]*A[1][1];for(LL i = 1; i <= N; ++i){for(LL j = 1; j <= M; ++j){for(LL k = 0; k <= 30*(i+j-1); ++k){if(f[i][j][k]){if(i < N){dp[i+1][j][k+A[i+1][j]] = min(dp[i+1][j][k+A[i+1][j]],dp[i][j][k]+A[i+1][j]*A[i+1][j]);f[i+1][j][k+A[i+1][j]] = 1;}if(j < M){dp[i][j+1][k+A[i][j+1]] = min(dp[i][j+1][k+A[i][j+1]],dp[i][j][k]+A[i][j+1]*A[i][j+1]);f[i][j+1][k+A[i][j+1]] = 1;}}}}}LL ans = 0xfffffffffff0;for(LL i = 0; i <= 30*(N+M-1); ++i)if(f[N][M][i])ans = min(ans,(N+M-1)*dp[N][M][i] - i*i);printf("Case #%d: %I64d\n",++kase,ans);}return 0;
}

这篇关于HDU5492 Find a path【DP】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---