3046.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 49 行

Problem Id:3046  User Id:fzk 
Memory:39240K  Time:871MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>

int c[1001];
int ans[1001][10000];

int main() {
	int i, j, k, sum, n, a, t, left, right;
	scanf( "%d%d%d%d", &n, &a, &left, &right );

	if( a > 10000 )
		while( printf( "asdf" ) );

	for( i=0; i<n; i++ )
		c[i] = 0;
	for( i=0; i<a; i++ ) {
		scanf( "%d", &t );
		c[t-1]++;
	}

	memset( ans, 0, sizeof ans );
	ans[0][0] = 1;
	sum = 0;

	for( i=0; i<n; i++ ) {
		for( j=0; j<=right && j<=sum; j++ ) {
			for( k=0; k<=c[i]; k++ ) {
				ans[i+1][j+k] += ans[i][j];
				ans[i+1][j+k] %= 1000000;
			}
			
		}
		sum += c[i];
	}

	sum = 0;
	for( i=left; i<=right; i++ )
		sum += ans[n][i];
	printf( "%d\n", sum%1000000 );
	return 0;
}