yukicoder : No.266 最終進化を目指せ

北海道の夜涼しい。20度切ってる。
http://yukicoder.me/problems/596

問題

問題文の解読にかなり苦戦したので、元問題文からだいぶ意訳した。

カードにはレベル(0～N)と能力がある。
レベルkのカードの能力値の上限はS[k]である。

あるカードに別のカードをもう１枚合成することで、以下の効果を得られる。

• 進化：あるカードにレベル0のカードを合成することで、前者のカードのレベルを1上げたカードを得ることができる。能力はそのまま。
• 強化：同レベルのカードを２枚合成することで、レベルは同じで、能力はmin(レベル上限,２枚の和＋１)のカード得ることができる。

レベルNのカードのうち、能力がiのものを得るのに必要な初期カード(レベル0能力0)の最少カード枚数をそれぞれ求めよ。

解法

F(l,s)をレベルl,能力sのカードを１枚得るのに必要な初期カード枚数とする。
F(l,s)はDPで以下のうち最小値を求めていけばよい。

• 進化で得る場合、F(l,s) = F(l-1,s) + 1
• 強化で得る場合、能力xと(s-1-x)のカードを合成するとしてF(l,s) = F(l,x) + F(l,s-1-x)

int N;
int S[101];
ll dp[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) cin>>S[i];
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=1;
	for(i=0;i<=N;i++) {
		FOR(j,S[i]+1) {
			if(i) dp[i][j]=dp[i-1][j]+1;
			for(x=0;x<j;x++) dp[i][j]=min(dp[i][j],dp[i][x]+dp[i][j-1-x]);
		}
	}
	
	FOR(i,S[N]+1) _P("%lld%c",dp[N][i],(i==S[N])?'\n':' ');
}

まとめ

ノートPCと不安定なWifiで解いたり文章書くのしんどい。
やっぱりCF315はやめとこうかな。