[TIOJ] 1734. 連鎖反應

題目連結:http://tioj.infor.org/problems/1734
感覺可以數學解解掉,不過還是寫了個$O(nk)$的DP作法。狀態應該不難想,就是$dp[i][j]$代表有幾顆球,且目前結尾有幾顆黑球,轉移的話就枚舉要放黑球或白球即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 20 + 5;

int dp[N][N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, k;
	while(cin>>n>>k){
		if(n<k) cout<<(1<<n)<<'\n';
		else if (n==k) cout<<((1<<n)-1)<<'\n';
		else{
			fill(dp[0], dp[n]+k+1, 0);
			dp[1][0]=1;
			dp[1][1]=1;
			for(int i=1;i<n;i++){
				for(int j=0;j<k;j++){
					dp[i+1][0] += dp[i][j];
					dp[i+1][j+1] += dp[i][j];
				}
			}
			int ans=0;
			for(int j=0;j<k;j++) ans+=dp[n][j];
			cout<<ans<<'\n';
		}
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology