hdu Chopsticks

80 阅读 0 评论 53 点赞

我是靠谱客的博主爱笑冰淇淋，这篇文章主要介绍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] 读者可以自己试验一下。（因为毕竟是要求三根筷子中较短两根筷子的差的平方。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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;
}