HDU 1500 Chopsticks

86 阅读 0 评论 57 点赞

我是靠谱客的博主含糊蛋挞，这篇文章主要介绍HDU 1500 Chopsticks，现在分享给大家，希望可以做个参考。

一道不算是很难的DP，一些人的爱好还真是奇怪的说！

嘿嘿

先变成非递增序列，因为要保证有一个最大的C在每一组里面。

转移方程： dp[i][j] = Min(dp[i][j-1] , dp[i-1][j-2] + (set[j-1 - set[j] )* (set[j-1] -set[j]))

第i个人第j个筷子的时候的最小值

复制代码

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