首页 > 代码库 > 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 }
View Code

 

hdu 4540 威威猫系列故事——打地鼠