hdu1500 Chopsticks DP和下面的hdu1421搬寝室差不多

92 阅读 0 评论 61 点赞

我是靠谱客的博主善良板栗，这篇文章主要介绍hdu1500 Chopsticks DP和下面的hdu1421搬寝室差不多，现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int min(int a,int b){return a<b?a:b;}
int dp[2001][5010];
int main()
{
	int n,i,k,a[5010],j,t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&k,&n);
		k+=8;
		for(i=n;i>0;i--)
			scanf("%d",&a[i]);
		for(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(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;
}