！HDU 1500 Chopsticks-dp-（分组问题）

题意：一种新式筷子：每副有三支，两支短的，长度差要尽可能小；一支长的，只要满足是一副里最长的就行。在n支筷子里选k副，要求每副里的短筷子的长度差总和最小

分析：

分组dp模型。这题跟搬寝室那题差不多，但这题的每组里多了一个长筷子，所以排序的时候从大到小，这样才能在一遍dp的时候一遍把长的选进每一组里，具体怎么实现的不要过于钻牛角尖。

正如搬寝室里总结的分组模型的实现方式有两种，这里也给出两个代码。注意具体实现上的一些细节差异，还有初始化。

把两道题结合起来看加深理解。

代码1：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define min(a,b) a<b?a:b;
#define INF 1000000007
using namespace std;
int t,k,n;
int dp[5010][1100],a[5100];
bool cmp(int i,int j)
{
return i>j;
}
int main()
{
cin>>t;
while(t--){
cin>>k>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,cmp);
k+=8;
for(int i=0;i<=n;i++)
for(int j=1;j<=k;j++)
dp[i][j]=INF;
for(int i=0;i<=n;i++) dp[i][0]=0;
for(int i=3;i<=n;i++){
for(int j=1;j*3<=i;j++){
dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
}
}
cout<<dp[n][k]<<endl;
}
}

#include<iostream>
#include<algorithm>
#include<cstring>
#define min(a,b) a<b?a:b;
using namespace std;
int t,k,n;
int dp[1010][5100],a[5100];
bool cmp(int i,int j)
{
return i>j;
}
int main()
{
cin>>t;
while(t--){
cin>>k>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,cmp);
memset(dp,0,sizeof(dp));
k+=8;
for(int i=1;i<=k;i++){
dp[i][3*i]=dp[i-1][3*i-2]+(a[3*i]-a[3*i-1])*(a[3*i]-a[3*i-1]);
for(int j=3*i+1;j<=n;j++)
dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]));
}
cout<<dp[k][n]<<endl;
}
}

最后

以上就是尊敬外套为你收集整理的！HDU 1500 Chopsticks-dp-（分组问题）的全部内容，希望文章能够帮你解决！HDU 1500 Chopsticks-dp-（分组问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。