2522.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include "iostream"
using namespace std;
int ans[230][11];
int get( int a, int b )
{
	int i;	
	if( b == 1 ) return 1;
	if( ans[a][b] < 0 )
	{
		ans[a][b] = 0;
		for( i=0; i*b<=a; i++ )
			ans[a][b] += get( a-i*b, b-1 );
	}
	return ans[a][b];
}
int main()
{
	int cas,n,m,k,s,i,j,t;
	for( i=0; i<=220; i++ )
	for( j=0; j<=10; j++ )
	ans[i][j] = -1;
	cin>>cas;
	while( cas-- )
	{
		cin>>m>>n>>k;
		m -= n;s=0;t=1;
		while( n > 1 )
		{
			
			for(i=0 ; s + get( m-i*n, n-1 ) < k; i++ )
			{
				s += get( m-i*n, n-1 );
			}			
			printf( "%d\n", i+t );
			t += i;
			m -= i*n;
			n--;		}
		printf( "%d\n", m+t );
	}
	return 0;
}