裏紙

ほぼ競プロ、たまに日記

AOJ 1335 - Equal Sum Sets

・概要

n(\leq 20)以下の自然数k(\leq 10)個使って和がs(\leq 155)になる組み合わせの数を求めよ。(ただしk個の数は互いにすべて異なる)

・アイデア

ー ループは書けないからDFSしよう

ー そのままだと多すぎて間に合わない,O(2^n)

ー だからメモ化しよう...今何個目を足しているか,和からすでに足した数を引いた値,1つ前に足した数を状態として持つ,O(n*s*n)=O(sn^2)

・実装(c++)

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

long dp[21][156][21]; //dp[何個目まで足したか][残ってる数][前に足した数]
int n, k;

long rec(int a, int b, int c){ //a番目,残りb,前に足した数c
	if(dp[a][b][c]>=0) return dp[a][b][c];
	
	long ret=0;
	if(a==k && b>=0){
		if(b==0) ret=1;
		else ret=0;	
	}
	else if(b<0) ret=0;
	else{
		for(int i=c-1; i>0; --i) ret+=rec(a+1, b-i, i);
		//printf("%d %d = %ld\n", a, b, ret);
	}
	//printf("ret dp[%d][%d] = %ld\n", a, b, ret);
	return dp[a][b][c]=ret;
}

int main(){
	while(1){
		int s;
		scanf(" %d %d %d", &n, &k, &s);
		if(n==0) break;	
		
		memset(dp, -1, sizeof(dp));
		printf("%ld\n", rec(0, s, n+1) );
	}
	return 0;
}

 とても基本的なことなのだが,メモ化再起をする際のメモの配列はrec関数と同じだけの値が必要だというとても当たり前のことを見落とし,4時間ほど悩んだ()ので,そういうことがないようにしなければという戒めと,なんかこのブログの機能の凄さを感じてみたくて書いた。笑
本当にrec関数は変数3個なのに,メモの配列はaとbの値しか持たずに計算してたら,まあ当たり前だが計算も合わず,何時間も悩んでしまうという結果に。再起苦手です。。意識を変えていきたいが。。
 DPは更に苦手というかどう書いていいかわかってないんですね。。春休みでいよいよ理解したいのだが。。