AOJ 0537 Bingo

• 概要

日本語の問題なので省略させていただきます。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0537

• 解法

動的計画法です。

dp[i][j]

i:マスの番号(左上から順に振ったとき)

j:i番目までの値の合計

というDPテーブルでソースコードのように回すだけです。

毎回余りを計算することでオーバーフローしません。

#include<cstdio>
#include<cstring>
#define mod 100000
using namespace std;

int dp[50][3001];
int main()
{
	int n,m,s;
	while(scanf("%d%d%d",&n,&m,&s),n){
		n*=n;
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=1;i<=m;i++){
			for(int j=n;j>0;j--){
				for(int l=i;l<=s;l++){
					dp[j][l]=(dp[j][l]+dp[j-1][l-i])%mod;
				}
			}
		}
		printf("%d\n",dp[n][s]);
	}
	return 0;
}