搬寝室(动态规划)
搬寝室(动态规划)
1944864971 发表于2年前
搬寝室(动态规划)
  • 发表于 2年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】新注册用户域名抢购1元起>>>   

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 0x3f3f3f3f
using namespace std;
int dp[2500][1500],Goods[2500];
int main()
{
int N,M;
while(~scanf("%d%d",&N,&M))
{
memset(Goods,0,sizeof(Goods));//每组数据重新置为零
for(int i=0; i<=N; i++)
for(int j=1; j<=M; j++)
dp[i][j]=MAX;//因为是求最小的疲劳度,有些数据用不到,所以将所有的数据先设为最大值
dp[0][0]=0;
for(int i=1; i<=N; i++)
scanf("%d",&Goods[i]);
sort(Goods,Goods+N+1);//按货物的重量排序,这样相邻的差值最小,
for(int i=2; i<=N; i++)
for(int j=1; 2*j<=i; j++)
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(Goods[i]-Goods[i-1])*(Goods[i]-Goods[i-1]));/*每次增加一个物品时,这个物品都有两种状态,取或不取,如果不去,则和在(i-1)个物品中选取j对是一样的,如果第i个物品去了,那么第(i-1)个物品一定要取,因为他们是相邻的,因为相邻的差值最小嘛,此时相当于在(i-2)个物品中取(j-1)对再加上最后一对;*/
printf("%d\n",dp[N][M]);

}

return 0;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: