以前虽然写过dp问题,但思想上过不去,觉得dp跟递归似乎是一样的,今天写过这道题后才顿悟:dp与递归不是一样的。状态方程dp[n][k]=min(dp[n-1][k],dp[n-2][k-1]+(w[i]-w[j])^2);唉,终于发现思想上有所改变了,不过代码实现能力不足,在对dp[]数组初始化的问题上浪费了n多精力和时间(当然浪费这么多精力也因事先没考虑好初始化后会有的漏洞),嗯,加点注释
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
int dp[2010][1010];
int weight[2010];
int main()
{
int n, k;
while(scanf("%d%d", &n, &k)!=EOF)
{
memset(dp, 0, sizeof(dp));
int i, j;
for( i=0;i<=n;i++)
for(j=((i/2)+1); j<=1000;j++)
dp[i][j] = INT_MAX/2; //dp数组的初始化,
//由于以后可能加值后用作比较,
//故赋值为最大值的一半
memset(weight, 0, sizeof(weight));
for(i=1;i<=n;i++)
scanf("%d", &weight[i]);
qsort(weight+1, n, sizeof(int), cmp);
for(i=2;i<=n;i++)
for(j=1;j<=k;j++)
{
int dp1, dp2; //dp过程中的两个选择状态
dp1 = dp[i-2][j-1]+(weight[i]-weight[i-1])*(weight[i]-weight[i-1]);
dp2 = dp[i-1][j];
dp[i][j] = dp1 < dp2 ? dp1 : dp2; //取较小的
}
printf("%d\n", dp[n][k]);
}
return 0;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间...
动态规划DP题解 POJ HDU部分动态规划DP题解
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦