hdu Chopsticks

点击打开链接

题目分析：

些题大概意思是说，有N条不同长度的筷子，在题目中按照非递减的顺序输入。

要求找出K+8 对（每对三根筷子使得每一对的最后两根的差的平方总和最少。）并输出最少值。

看起来，这和搬寝室那一题差不多。

状态转移方程可表示为；

dp[i][j]=min(dp[i][j-1],dp[i-1][j-2]+(a[j]-a[j-1])^2;

这里为什么是dp[i-1][j-2] 读者可以自己试验一下。（因为毕竟是要求三根筷子中较短两根筷子的差的平方。

#include<stdio.h>
#include<string.h>
int dp[1001][5001];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
int i,j,k,n,a[5001],t;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
scanf("%d%d",&k,&n);
for(i=n;i>0;i--) scanf("%d",&a[i]);
k+=8;
for(i=1;i<=k;i++)
{
dp[i][i*3]=dp[i-1][i*3-2]+(a[i*3]-a[i*3-1])*(a[i*3]-a[i*3-1]);
for(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]));
}
printf("%dn",dp[k][n]);
}
return 0;
}

最后

以上就是爱笑冰淇淋为你收集整理的hdu Chopsticks的全部内容，希望文章能够帮你解决hdu Chopsticks所遇到的程序开发问题。

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