hdu 1241 搬寝室 水dp
2024-08-27 04:10:31
搬寝室
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2*k件过去就行了.但还是会很累,因为2*k也不小是一个不大于n的整数.幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比(这里补充一句,xhd每次搬两件东西,左手一件右手一件).例如xhd左手拿重量为3的物品,右手拿重量为6的物品,则他搬完这次的疲劳度为(6-3)^2 = 9.现在可怜的xhd希望知道搬完这2*k件物品后的最佳状态是怎样的(也就是最低的疲劳度),请告诉他吧.
Input
每组输入数据有两行,第一行有两个数n,k(2<=2*k<=n<2000).第二行有n个整数分别表示n件物品的重量(重量是一个小于2^15的正整数).
Output
对应每组输入数据,输出数据只有一个表示他的最少的疲劳度,每个一行.
Sample Input
2 1
1 3
1 3
Sample Output
4
Author
xhd
Source
思路:dp[i][t]=min(dp[i-1][t],dp[i-2][t-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
#include<bits/stdc++.h>
using namespace std;
#define ll __int64
#define mod 1000000007
#define pi (4*atan(1.0))
const int N=2e3+,M=1e6+,inf=1e9+;
int a[N];
int dp[N][N];
int main()
{
int x,y,z,i,t;
while(~scanf("%d%d",&x,&y))
{
for(i=;i<=x;i++)
for(t=;t<=y;t++)
dp[i][t]=inf;
for(i=;i<x;i++)
for(t=;t<=i/;t++)
dp[i][t]=;
for(i=;i<=x;i++)
scanf("%d",&a[i]);
sort(a+,a+x+);
dp[][]=(a[]-a[])*(a[]-a[]);
for(i=;i<=x;i++)
for(t=;*t<=i&&t<=y;t++)
dp[i][t]=min(dp[i-][t],dp[i-][t-]+(a[i]-a[i-])*(a[i]-a[i-]));
printf("%d\n",dp[x][y]);
}
return ;
}
最新文章
- redis启用持久化
- [转]Oracle版本号解释
- PHPExcel 导出表格 不知道好不好用
- PAT (Basic Level) Practise:1028. 人口普查
- 【java】: 操作excel2007/2003
- 响应式js幻灯片代码一枚
- Mesa10.2在Win7上的编译
- ARM指令分类学习
- Python运行Google App Engineer时出现的UnicodeDecodeError错误解决方案
- 让iframe调用页面的背景透明
- ueditor使用注意事项
- 在windows下运行spark
- Docker笔记四:Elasticsearch实例部署
- 最小可用id
- docker开发实践
- python 使用多进程打开多个cmd窗口,并在子进程结束之后关闭cmd窗口
- react-踩坑记录——Link带参数跳转后this.props为空对象
- JS基础-数组的常用方法-冒泡排序
- Spring Boot --- Swagger基本使用
- CentOS6.9 安装Oracle 11G 版本11.2.0.1.0
热门文章
- Commons Email使用
- Windows上安装Node.js
- flatpickr功能强大的日期时间选择器插件
- 解决Centos关闭You have new mail in /var/spool/mail/root提示(转)
- 斯坦福第二课:单变量线性回归(Linear Regression with One Variable)
- appium 中手势密码的定位坐标
- Delphi APP 開發入門(三)簡易計算機
- Log4net 自定义字段 写入Oracle 使用ODP.NET Managed驱动
- 404 Not Found 探秘Nginx转发处理流程
- Java反射在整个程序运行中的位置