hdu1421 dp
2024-09-06 15:49:55
用dp[i][j]表示放了i件物品,j对时的最小值。
dp[i-2][j-1]表示取当前的 dp[i-1][j]表示不取当前的。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 2002
#define INF 99999999
int dp[maxn][],a[maxn];
int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
int i,j,n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(i=;i<=n;i++)
scanf("%d",&a[i]);
sort(a+,a+n+); memset(dp,,sizeof(dp)); for(i=;i<=n;i++){
for(j=;j<=k;j++){
dp[i][j]=INF;
}
}
for(i=;i<=n;i++)
{
dp[i][]=;
} for(i=;i<=n;i++)
{
for(j=;j<=k;j++)
{
//dp[i-2][j-1]表示取当前的 dp[i-1][j]表示不取当前的
dp[i][j]=min(dp[i-][j-]+(a[i]-a[i-])*(a[i]-a[i-]),dp[i-][j]);
}
}
printf("%d\n",dp[n][k]);
}
}
/*
3 1
2 5 6
5 2
1 3 4 7 8
*/
最新文章
- $.each ---- 跳出当前的循环
- SMO推导和代码-记录毕业论文4
- 使用nginx绑定域名,代理gitlab
- MySQL(三) —— 约束以及修改数据表
- MVC 3 基本操作增加修改
- 可视化swing界面编辑--转载
- JAVA入门第二季(mooc-笔记)
- 基于网络的服装定制MTM系统研究 - 硕士论文 - 道客巴巴
- MySql开启远程访问(Linux)
- PAT1008
- MySQL C#教程
- 阿里云centos配置postfix
- int指令
- JAVA 中的接口(interface)
- JavaScript高级程序设计学习(四)之引用类型(续)
- 反射API(二)
- leetcode-爬楼梯(动态规划)
- Climbing Stairs爬楼梯——动态规划
- 数据挖掘Apriori算法——学习笔记
- Settings app简单学习记录