[UVa] 10313 - Pay the Price

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

題意:
(from luckycat)


解法:
經典 DP 問題，求換錢的方法數。

TAG: DP, subset sum

注意: 要用 long long

程式碼:

	/**
	* Tittle: 10313 - Pay the Price
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/16
	*/
	// 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 305
	typedef long long ll;
	// declarations
	ll dp[1005][N];
	ll pre[1005][N];
	int n, l, r;
	// functions
	void init( void )
	{
	clr( dp, 0 );
	dp[0][0] = 1LL;
	FOR( j, 1, 300 ) {
	FOR( i, 1, 300 ) {
	FOR( k, 0, 300-j ) if( dp[i-1][k] ) {
	dp[i][k+j] += dp[i-1][k];
	}
	}
	}
	clr( pre, 0 );
	FOR( i, 0, 300 )
	pre[0][i] = dp[0][i];
	FOR( i, 0, 300 )
	FOR( j, 1, 1000 )
	pre[j][i] = pre[j-1][i]+dp[j][i];
	}
	void input( void )
	{
	l = r = -1;
	char buf[100];
	gets(buf);
	stringstream ss(buf);
	ss >> l >> r;
	}
	void solve( void )
	{
	if( l==-1 ) {
	r = n;
	} else {
	if( r==-1 ) {
	r = l;
	l = -1;
	} else {
	--l;
	}
	}
	if( l==-1 ) printf( "%lld\n", pre[r][n] );
	else printf( "%lld\n", pre[r][n]-pre[l][n] );
	}
	// main function
	int main( void )
	{
	init();
	// input
	while( scanf( "%d", &n )==1 ) {
	input();
	solve();
	}
	return 0;
	}

view raw 10313 - Pay the Price.cpp hosted with ❤ by GitHub