首页 > 代码库 > HDU 5492 Find a path
HDU 5492 Find a path
题意：
在一张N*M的图上，每个点都有权值，寻找一条从（1,1）到（n，m）的路径，使得
(n+m-1)*sigma(Ai-Aavg)最小
其中Aavg是路径上Ai的平均数
题解
看题目是一个DP，但是路径平均值得存在使得状态很难定义。
所以我们进行变形，将和式展开之后，得到ans=(n+m-1)*S1-S2;
其中S1是路径上所有数的平方和，S2为路径上数的和的平方。
也就是要求S1最小的同时S2最大。
dp[i][j][s]表示到达(i,j)时平方和为s时和的的最小值，答案通过枚举所有s取得
#include<bits/stdc++.h>#define clr(x,y) memset((x),(y),sizeof(x))using namespace std;typedef long long LL;const int maxn=30;const int inf=1e8;int mp[maxn+5][maxn+5];int dp[maxn+5][maxn+5][2*maxn*maxn+5];int n,m;void solve(int iCase){ scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) { for (int j=1;j<=m;++j) { scanf("%d",&mp[i][j]); } } for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) for (int k=0;k<=2*maxn*maxn;++k) dp[i][j][k]=inf; dp[1][1][mp[1][1]]=mp[1][1]*mp[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=0;k<=2*maxn*maxn;++k) { if (i-1>=1 && k>=mp[i][j]) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-mp[i][j]]+mp[i][j]*mp[i][j]); if (j-1>=1 && k>=mp[i][j]) dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-mp[i][j]]+mp[i][j]*mp[i][j]); } } } int ans=inf; for (int k=0;k<=2*maxn*maxn;++k) { if (dp[n][m][k]==inf) continue; int tmp=(n+m-1)*dp[n][m][k]-k*k; ans=min(ans,tmp); } printf("Case #%d: %d\n",iCase,ans);}int main(void){ #ifdef ex freopen ("../in.txt","r",stdin); //freopen ("../out.txt","w",stdout); #endif int T; scanf("%d",&T); for (int i=1;i<=T;++i) { solve(i); }}
HDU 5492 Find a path
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。