题目：http://acm.hdu.edu.cn/showproblem.php?pid=1500
从大到小搞，到第 i 个人取的对数 不超过 i/3，就保证了对于每一对之前总有比他大的 与他配对。
|
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 |
#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("%d\n",dp[n][k]); } return
0;} |
Chopsticks Hdu1500,布布扣,bubuko.com
原文：http://www.cnblogs.com/yigexigua/p/3782071.html