UVA 10271 佳佳的筷子 Chopsticks [DP的基本运用]

佳佳的筷子 Chopsticks

题面翻译

定义一个三元组$(a,b,c)(a⩽b⩽c)$，它的权值为 $(a-b{)}^2$
。 给定 $n(n⩽5000)$ 个数，要求选出 $k+8$ 个三元组，使得这$k+8$个三元组权值和最小。

输入数据是单调递增的。

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

1
1 40
1 8 10 16 19 22 27 33 36 40 47 52 56 61 63 71 72 75 81 81 84 88 96 98
103 110 113 118 124 128 129 134 134 139 148 157 157 160 162 164
1
2
3
4

样例输出 #1

23
1

分析

考虑DP，如果如果当前筷子不选：

f[i][j]=f[i-1][j];
1

如果选当前筷子，和前面一支筷子算权值：

f[i][j]=f[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]);
1

然后比较两者的大小，取小的：

f[i][j]=min(f[i-1][j],f[i-2][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]))
1

我们要差的平方最小，所有必须是相邻筷子，差最小，差的平方也最小，所以筷子必须是排列好的，我们就可以考虑升序降序。
这里有三根筷子，而且长度依次递增，但是这里如果用升序不好实现选三根，所以我们用降序。
这里的权值又和最长的那一根筷子没关系，所以直接降序，看后面两根筷子的差的平方差。

代码

#include

using namespace std;

int a[1000000];

int f[10000][10000];

int n,k;

int T;

int main()
{
	cin>>T;
	
	while(T--)
	{
	
		cin>>k>>n;
	
		k+=8;
	
		for(int i=n;i>=1;i--)
		{
			cin>>a[i];
		}
	
		memset(f,0x3f3f3f,sizeof(f));
	
		for(int i=0;i<=n;i++)
		{
			f[i][0]=0;
		}
	
		for(int i=3;i<=n;i++)
		{
			for(int j=1;j<=k;j++)
			{
				if(i>=3*j)
				{
					f[i][j]=min(f[i-1][j],f[i-2][j-1]+ (a[i-1]-a[i])*(a[i-1]-a[i]) );
				}
			}
		}
		
		cout<<f[n][k]<<endl;
	}
    
    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
41
42
43
44
45
46
47
48
49
50
51