[HDU 1421]搬寝室(富有新意的DP)
2024-08-26 11:32:00
题目地址: pid=1421" target="_blank">http://acm.hdu.edu.cn/showproblem.php? pid=1421
题目大意:给出n个物品,要你选出k对物品。使得每对物品之差的平方之和最小。
思路。动态规划求解。首先将物品按重量升序排序,依据贪心思想,每对物品必定是相邻的两个物品,这样重量差的平方才干保证最小。然后DP,用f[i][j]表示前i个物品,选j对的最少代价,这里须要进行一个重要的分类讨论:
(1)假设j*2=i,即前i个物品所实用于配对了,非常明显第j对物品是第i-1号物品和第i号物品,f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])^2
(2)其它情况。前i个物品并没有全然用于配对。能够选择第i个物品不配对。这时f[i][j]=f[i-1][j]。或者第i个物品參与配对,同(1)。第i个物品和第i-1个物品配对,f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])^2
终于的答案就是f[n][k]
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm> #define MAXN 2010 using namespace std; int f[MAXN][MAXN]; //f[i][j]=前i个物品。选j对的最小花费
int w[MAXN]; int min(int a,int b)
{
if(a<b) return a;
return b;
} int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(f,0,sizeof(f));
w[0]=0;
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
sort(w+1,w+n+1);
for(int i=2;i<=n;i++) //前i个物品
for(int j=1;j*2<=i;j++) //选j对
{
if(i!=2*j) f[i][j]=min(f[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]),f[i-1][j]); //要么第i个物品和第i-1个物品配对。要么留着第i个物品不配对
else f[i][j]=f[i-2][j-1]+(w[i]-w[i-1])*(w[i]-w[i-1]);
}
printf("%d\n",f[n][k]);
}
return 0;
}
最新文章
- Git异常:fatal: could not create work tree dir &#39;XXX&#39;: No such file or directory
- 【NOIP2013】火柴排队
- 配置Tomcat的JVM的大小解决Tomcat内存溢出的问题
- 卸载sqlserver数据库参考
- 如何在 CentOS 7 上安装 Redis 服务器
- 关于SQL server的一些知识点
- HHKB Professional 2
- Debian 使用杂记(一)
- NODE.JS安装配置
- linux mint运行docker
- python - 常用模块栗子
- Natas Wargame Level27 Writeup(SQL表的注入/溢出与截取)
- 嵌入式linux------SDL移植(am335x下显示bmp图片)
- Kafka学习笔记2: 快速入门
- 洛谷:P1036:选数
- 时序数据库InfluxDB安装及使用
- Ringo替换Paul
- CSS效果:简单的登录框
- Git使用(一、TortoiseGit和Gitlab在Windows下的项目库创建和上传)
- SharePoint REST 服务获取讨论版问题