Chopsticks Hdu1500

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1500

从大到小搞，到第 i 个人取的对数 不超过 i/3，就保证了对于每一对之前总有比他大的 与他配对。

复制代码#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <queue> #include <vector> #include <map> #include <string> #include <iostream> using namespace std; const int INF=0xfffffff; int Min(int a,int b) { return a>b? b:a; } int a[5555],dp[5555][1111]; int main() { int acase,n,k; scanf("%d",&acase); while(acase--){ scanf("%d%d",&k,&n);k+=8; for(int i=n;i>0;i--) scanf("%d",&a[i]); for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j]=INF; for(int i=0;i<=n;i++) dp[i][0]=0; for(int i=1;i<=n;i++) for(int j=1;j<=i/3;j++){ dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])); } printf("%dn",dp[n][k]); } return 0; }

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
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
const int INF=0xfffffff;
int Min(int a,int b)
{
	return a>b? b:a;
}
int a[5555],dp[5555][1111];
int main()
{
	int acase,n,k;
	scanf("%d",&acase);
	while(acase--){
		scanf("%d%d",&k,&n);k+=8;
		for(int i=n;i>0;i--)
			scanf("%d",&a[i]);
		for(int i=0;i<=n;i++)
			for(int j=0;j<=k;j++)
			dp[i][j]=INF;
		for(int i=0;i<=n;i++)
			dp[i][0]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=i/3;j++){
			dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
		}
		printf("%dn",dp[n][k]);
	}
	return 0;
}