首页 > 代码库 > hdu 4540 威威猫系列故事——打地鼠
hdu 4540 威威猫系列故事——打地鼠
http://acm.hdu.edu.cn/showproblem.php?pid=4540
dp公式: dp[i][j]=min(dp[i][j],dp[i-1][c]+abs(a[i][j]-a[i-1][c]));
dp[i][j] 表示:第i时刻第j个地鼠的最小能量。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll long long 5 #define maxn 10000 6 using namespace std; 7 const ll mod=1000000000+7; 8 const int inf=1<<29; 9 10 int t;11 int n,m,k;12 int a[1000][1000];13 int dp[100][100];14 15 16 int main()17 {18 while(scanf("%d%d",&n,&k)!=EOF)19 {20 for(int i=1; i<=n; i++)21 {22 for(int j=1; j<=k; j++)23 {24 scanf("%d",&a[i][j]);25 }26 }27 for(int i=1; i<=n; i++)28 {29 for(int j=1; j<=k; j++)30 {31 dp[i][j]=inf;32 }33 }34 for(int i=1; i<=k; i++)35 {36 dp[1][i]=0;37 }38 for(int i=2; i<=n; i++)39 {40 for(int j=1; j<=k; j++)41 {42 for(int c=1; c<=k; c++)43 {44 dp[i][j]=min(dp[i][j],dp[i-1][c]+abs(a[i][j]-a[i-1][c]));45 }46 }47 }48 int ans=inf;49 for(int i=1; i<=k; i++)50 {51 ans=min(ans,dp[n][i]);52 }53 printf("%d\n",ans);54 }55 return 0;56 }
hdu 4540 威威猫系列故事——打地鼠
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。