[UVa] 10326 - The Polynomial Equation

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

題意:
(from luckycat)


解法:
因為 n 最大到 50，所以暴力計算是沒辦法的喔。
所以要利用 DP 來解，舉個例子，如果一個方程式的根是 a、b、c 的話，
方程式則為 (x-a)(x-b)(x-c) = 0，展開得 x^3 - (a+b+c) x^2 + (ab+bc+ca) x - abc = 0，
我們定義 dp[ i ][ j ] 為 我們討論前 i 個根以第 i 個根為結尾且總共有 j 個數(包含 i )的乘法，則遞迴定義：

dp[ i ][ j ] = 
{ num[ i ], if j = 1 & i > 0
{ sum( dp[ k ][ j - 1 ] * num[ i ], 1 <= k < i ), if j > 1 & i > 0

舉例：如上的假設 依序將 a、b、c 設為 1、2、3。
從一開始。
dp[ 1 ][ 1 ] = a
dp[ 2 ][ 1 ] = b
dp[ 2 ][ 2 ] = dp[ 1 ][ 1 ] * num[ 2 ] = a * b
dp[ 3 ][ 1 ] = c
dp[ 3 ][ 2 ] = dp[ 1 ][ 1 ] * num[ 3 ] + dp[ 2 ][ 1 ] * num[ 3 ] = a * c + b * c
dp[ 3 ][ 3 ] = dp[ 2 ][ 2 ] * num[ 3 ] = ( a * b ) * c
由這樣就可以得出
第一項 = 1
第二項 = dp[ 1 ][ 1 ] + dp[ 2 ][ 1 ] + dp[ 3 ][ 1 ]
第三項 = dp[ 2 ][ 2 ] + dp[ 3 ][ 2 ]
第四項 = dp[ 3 ][ 3 ]

TAG: Math, DP

注意:

程式碼:

	/**
	* Tittle: 10326 - The Polynomial Equation
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/17
	*/
	// 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 N 55
	typedef long long ll;
	// declarations
	int n;
	ll num[N];
	ll dp[N][N];
	ll coef[N];
	// functions
	void solve( void )
	{
	clr( dp, 0 );
	FOR( i, 1, n ) {
	dp[i][1] = num[i];
	FOR( j, 1, i-1 ) {
	FOR( k, 1, j )
	dp[i][k+1] += dp[j][k]*num[i];
	}
	}
	clr( coef, 0 );
	FOR( i, 1, n ) FOR( j, i, n )
	coef[i] += dp[j][i];
	// output
	putchar('x');
	if( n>1 ) printf( "^%d", n );
	FOR( i, 1, n-1 ) {
	if( coef[i]!=0LL ) {
	if( i&1 ) coef[i] = -coef[i];
	if( coef[i]<0LL ) {
	printf( " - " );
	coef[i] = -coef[i];
	} else printf( " + " );
	if( coef[i]>1LL ) printf( "%lld", coef[i] );
	printf("x");
	if( n-i>1 ) printf( "^%d", n-i );
	}
	}
	if( n&1 ) coef[n] = -coef[n];
	if( coef[n]<0LL ) printf( " - %lld", -coef[n] );
	else printf( " + %lld", coef[n] );
	puts(" = 0");
	}
	// main function
	int main( void )
	{
	// input
	while( scanf( "%d", &n )==1 ) {
	FOR( i, 1, n ) scanf( "%lld", &num[i] );
	solve();
	}
	return 0;
	}

view raw 10326 - The Polynomial Equation.cpp hosted with ❤ by GitHub