首页 > 代码库 > HDU 5492 Find a path (dp)
HDU 5492 Find a path (dp)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5492
每个数字只能走下或者走右，问你方差最小多少？
方差 = (n + m - 1) * sum(a[i]^2) + sum(a[i])
我们可以定义dp[i][j][k]为(i, j)点和为k的最小平方和，k最大也就(n-m+1)*30大小
那么可以dp[i][j][k - a[i][j]] = min(dp[i][j - 1][k], dp[i - 1][j][k]) + a[i][j]*a[i][j];
保证转移最优的话，那么需要初始化dp[i][j][k] = inf;
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e5 + 5;17 int dp[35][35][1805], a[35][35], inf = 1e6;18 19 int main()20 {21 int t, n, m;22 scanf("%d", &t);23 for(int ca = 1; ca <= t; ++ca) {24 scanf("%d %d", &n, &m);25 for(int i = 1; i <= n; ++i) {26 for(int j = 1; j <= m; ++j) {27 scanf("%d", &a[i][j]);28 for(int k = 0; k <= 1800; ++k) {29 dp[i][j][k] = inf;30 }31 }32 }33 int sum = 0;34 for(int i = 1; i <= n; ++i) {35 sum += a[i][1];36 dp[i][1][sum] = dp[i - 1][1][sum - a[i][1]] + a[i][1]*a[i][1];37 }38 sum = 0;39 for(int i = 1; i <= m; ++i) {40 sum += a[1][i];41 dp[1][i][sum] = dp[1][i - 1][sum - a[1][i]] + a[1][i]*a[1][i];42 }43 for(int i = 2; i <= n; ++i) {44 for(int j = 2; j <= m; ++j) {45 for(int k = a[i][j]; k <= 1800; ++k) {46 dp[i][j][k] = min(dp[i - 1][j][k - a[i][j]], dp[i][j - 1][k - a[i][j]]) + a[i][j]*a[i][j];47 }48 }49 }50 int ans = inf;51 for(int k = 0; k <= 1800; ++k) {52 if(dp[n][m][k] < inf) {53 ans = min(ans, dp[n][m][k] * (n + m - 1) - k*k);54 }55 }56 printf("Case #%d: %d\n", ca, ans);57 }58 return 0;59 }
HDU 5492 Find a path (dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。