[UVa] 10271 - Chopsticks

題目網址: https://goo.gl/V7UdPL

題意:
(from luckycat)


解法:
參考 http://www.cppblog.com/rakerichard/archive/2010/02/19/108081.html。

TAG: DP,

注意:

程式碼:

	/**
	* Tittle: 10271 - Chopsticks
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/02
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define pre(x) ((x-1)&1)
	#define cur(x) ((x)&1)
	#define INF 1e9
	#define N 5005
	#define K 1015
	// declarations
	int t;
	int k, n;
	int len[N];
	// functions
	int dp[2][N];
	int w( int i, int j )
	{
	int d = len[i]-len[j];
	return d*d;
	}
	void solve( void )
	{
	int ans;
	clr( dp[0], 0 );
	FOR( i, 1, k ) {
	FOR( j, 1, n ) {
	if( i*3 > j ) dp[cur(i)][j] = INF;
	else dp[cur(i)][j] = min(
	dp[cur(i)][j-1],
	dp[pre(i)][j-2]+w(j,j-1)
	);
	}
	}
	ans = INF;
	FOR( i, k*3, n ) ans = min( ans, dp[cur(k)][i] );
	printf( "%d\n", ans );
	}
	// main function
	int main( void )
	{
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d%d", &k, &n );
	k += 8;
	for( int i=n; i>=1; --i )
	scanf( "%d", &len[i] );
	solve();
	}
	return 0;
	}

view raw 10271 - Chopsticks.cpp hosted with ❤ by GitHub