首页 > 代码库 > hdu5492_枚举dp
hdu5492_枚举dp
题目大意：给N*M(1<=N，M<=30)的矩阵，矩阵的每一格有一个非负权值(<=30)
从(1，1)出发，每次只能向右或向下移动，到达(n，m)时，经过的格子的权值形成序列A，
求(N+M−1)∑N+M−1i=1(Ai−Aavg)2
的最小值。
参考链接：http://blog.csdn.net/u014679804/article/details/48769267
将式子展开后，化简整理可得：(N+M-1)*s1-s2。其中s1是序列A的平方和，s2是序列A的和的平方。
注意到序列A的和不会超过(30+30-1)*30。
设dp[i][j][k]表示到达(i，j)，序列和为k时，序列的平方和的最小值。
那么很容易得到状态转移方程，对于向右走，有：dp[i][j+1][k+V[i][j+1]]=min(dp[i][j+1][k+V[i][j+1]],dp[i][j][k]+V[i][j+1]*V[i][j+1])，V[i][j]为（i，j）的值，类似地，可得到向下走的状态转移方程。
最终，枚举(n+m-1)*dp[n][m][k]-k^2，0<=k<=59*30，取最小值即为答案。
注意dp的初始化，枚举序列A的和的时候，有些和是不会出现的，即有些状态是无法到达的。因此将dp全部初始化为inf，第(1,1)格的值初始化为V[1][1]^2，然后求解各个状态的值。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define inf 0x3f3f3f3f14 typedef long long LL;15 16 int dp[40][40][1800], a[40][40];17 int main()18 {19 int t, n, m;20 scanf("%d", &t);21 for(int ca = 1; ca <= t; ca++)22 {23 scanf("%d %d", &n, &m);24 for(int i = 1; i <= n; i++)25 for(int j = 1; j <= m; j++)26 scanf("%d", &a[i][j]);27 memset(dp, inf, sizeof(dp));28 dp[0][1][0] = 0;29 for(int i = 1; i <= n; i++)30 {31 for(int j = 1; j <= m; j++)32 {33 for(int k = a[i][j]; k <=59 * 30; k++)34 {35 if(dp[i-1][j][k-a[i][j]] != inf)36 dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-a[i][j]]+a[i][j]*a[i][j]);37 if(dp[i][j-1][k-a[i][j]] != inf)38 dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k-a[i][j]]+a[i][j]*a[i][j]);39 } 40 }41 }42 int res = inf;43 for(int i = 0; i <= 59 * 30; i++)44 {45 if(dp[n][m][i] != inf)46 res = min(res, (n+m-1)*dp[n][m][i]-i*i);47 }48 printf("Case #%d: %d\n", ca, res);49 }50 return 0;51 }
hdu5492_枚举dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。