uva10271 - Chopsticks（遞推）

uva10271 - Chopsticks（遞推）

題目：uva10271 - Chopsticks（遞推）

題目大意：給出N支筷子，值代表長度，現在要求在這些筷子中選出K對，每對筷子（A,B,C),badness(B- A）^2.要求總的badness最小。

解題思路：選擇相鄰的筷子來做A和B，這樣的badness肯定比較小。但是還要考慮C比較麻煩。最後看了大神的題接，筷子應該從長到短開始考慮，dp【k】【j】：前j根筷子湊出了K對，最小的badness。 dp【k】【j】 = Min （（dp【k】【j - 1】， dp【k - 1】【j - 2】 + badness（j - 1， j).看j這支筷子是否加入第k對。如果j加入的話，那麼j肯定是和j - 1湊一對，這樣badness比較小。然後因為是從大往小取，所以前面的肯定是比後面的長，所以只要看j 是否大於等於 3 * k，就可以排除C的干擾。

代碼：

#include 
#include 

typedef long long ll;
const int N = 5005;
const int M = 1010;
const ll INF = 1e13;

ll dp[M][N];
int c[N];

ll Min (const ll a, const ll b) { return a < b? a: b; }

int W (const int a, const int b ) { return (a - b) * (a - b); }

int main () {

	int t;
	int k, n;
	scanf ("%d", &t);
	while (t--) {
		
		scanf ("%d%d", &k, &n);
		for (int i = n; i >= 1; i--)
			scanf ("%d", &c[i]);
		k += 8;

		for (int i = 1; i <= n; i++)
			dp[0][i] = 0;
		for (int i = 1; i <= k; i++)
			for (int j = 1; j <= n; j++) {

				dp[i][j] = INF;
				if (i * 3 > j)
					continue;
				if (j - 2 >= 1)
					dp[i][j] = Min (dp[i][j], dp[i - 1][j - 2] + W(c[j], c[j - 1]));
				if (j - 1 >= 1)
					dp[i][j] = Min (dp[i][j], dp[i][j - 1]);
			}
		
		ll ans = INF;
		for (int i = 3 * k; i <= n; i++)
			ans = Min (ans, dp[k][i]);

		printf ("%lld\n", ans);
	}
	return 0;
}