SCU 1685 Chopsticks

[题目链接]http://acm.hdu.edu.cn/showproblem.php?pid=1500

题意：有N支筷子，要凑出K+8套的三支筷子，其中A<=B<=C，筷子(A-B)^2称为badness，求最小的总badness。

分析：先变成非递增序列，因为要保证有一个最大的C在每一组里面。dp[i][j]表示第i个人第j个筷子。dp[i][j]=min(dp[i-1][j],dp[i-1][j-2]+(a[j]-a[j-1])*(a[j]-a[j-1]));

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_K 1005
#define MAX_N 5005
#define inf 0x3f3f3f3f
using namespace std;
int dp[MAX_K][MAX_N];
int a[MAX_N];
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int k,n;
scanf("%d%d",&k,&n);
k+=8;
for(int i=n;i>=1;i--)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
{
dp[0][i]=0;
for(int j=1;j<=k;j++)
dp[j][i]=inf;
}
for(int i=1;i<=k;i++)
{
for(int j=i*3;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]));
}
}
printf("%dn",dp[k][n]);
}
return 0;
}

最后

以上就是高高毛豆为你收集整理的SCU 1685 Chopsticks的全部内容，希望文章能够帮你解决SCU 1685 Chopsticks所遇到的程序开发问题。

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