【题解】UVA10271：佳佳的筷子 Chopsticks

@luogu
贪心策略，如果知道当前一组筷子最小的那根，那么与他组合的肯定是与他相邻的，然后剩下那根最长的不用管
$d{p}_{i,j}$表示组了$j$组筷子，最后一组最短的筷子是第$i$根，倒着推导
$d{p}_{i,j}<---(a_i-a_{i+1}{)}^2+d{p}_{i+2,j-1}$
这样其实转移意义不明，换言之会有漏掉，可以改变定义，当前用了$i-n$这么多的筷子，最后一根筷子不一定是第$i$根
这样$d{p}_{i,j}<---d{p}_{i+1,j}$

Code：

#include <bits/stdc++.h>
#define maxn 5010
#define maxm 1010
using namespace std;
int a[maxn], dp[maxn][maxm], n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	int Q = read();
	while (Q--){
		m = read() + 8, n = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) dp[i][j] = 1e9;
		for (int j = 1; j <= m; ++j)
			for (int i = n - 2; i; --i){
				dp[i][j] = dp[i + 1][j];
				if (n - i + 1 >= 3 * j)
					dp[i][j] = min(dp[i][j], dp[i + 2][j - 1] + (a[i] - a[i + 1]) * (a[i] - a[i + 1]));
			}
		printf("%dn", dp[1][m]);
	}
	return 0;
}

最后

以上就是活泼山水为你收集整理的【题解】UVA10271：佳佳的筷子 Chopsticks的全部内容，希望文章能够帮你解决【题解】UVA10271：佳佳的筷子 Chopsticks所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。