佳佳的筷子 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

23

分析

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

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

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

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

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

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

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

代码

#include<bits/stdc++.h>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;
}