yukicoder No.412 花火大会
問題概要
組み合わせの数え上げ
解法
まず、すべてソートしてく。全探索をして、それぞれの家族がどのマットを使うかを決める。それが条件を満たしたものであれば、ほかのものは選ぶ選ばないの選択がある。
dpのほうがわかりやすいな。状態数は2つで、1つは、何枚目までを考えているか、もう一つは、条件を満たしている数である。
dp[i][j] := i番目のマットまでで考えて、j=1ならBのマットは条件を満たし、j=2ならBCのマットは条件を満たし、j=3ならすべてのマットの条件を満たすとしてやる。
漸化式は、i番目のマットが、新たに次の条件を満たす大きさであるなら(j=1なら次はc以上の大きさであれば条件を満たす)、i番目のマットを選べば新たに条件を満たし、選ばなければ新たに条件は増えないので、
dp[i + 1][j + 1] += dp[i][j];//選択する
dp[i + 1][j] += dp[i][j];//選択しない
となる。
条件を満たさないときは、i番目の選択の有無にかかわらず条件を満たすことはないので、
dp[i + 1][j] += 2 * dp[i][j];//選択するしないの2通り
となる
ミス
これは典型的dpなんですね。
コード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int main(void){ vector<int> s(3); int n; rep(i, 3) cin >> s[i]; cin >> n; sort(s.begin(), s.end()); vector<int> e(n); rep(i, n) cin >> e[i]; sort(e.begin(), e.end()); ll ans = 0; for (int i = 0; i < n; ++i){ for (int j = i + 1; j < n; ++j){ for (int k = j + 1; k < n; ++k){ if(s[0] <= e[i] && s[1] <= e[j] && s[2] <= e[k]){ //上記の3つ以外で条件を満たすものは使う使わないの2通りの方法を選ぶことができる ans += pow(2, i); } } } } printf("%lld\n", ans); }
dp
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cmath> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; //dp[i][j] := i番目のマットまでで考えて、 //j=1ならBのマットは条件を満たし、j=2ならBCのマットは条件を満たし、 // j=3ならすべてのマットの条件を満たす int dp[50][4]; int main(void){ vector<int> s(3); int n; rep(i, 3) cin >> s[i]; cin >> n; sort(s.begin(), s.end()); vector<int> e(n); rep(i, n) cin >> e[i]; sort(e.begin(), e.end()); dp[0][0] = 1; for (int i = 0; i < n; ++i){ for (int j = 0; j <= 3; ++j){ if(j < 3 && s[j] <= e[i]){//j個目に条件を満たすもととして選択可 dp[i + 1][j + 1] += dp[i][j];//選択する dp[i + 1][j] += dp[i][j];//選択しない }else{//選択しても条件は満たさない dp[i + 1][j] += 2 * dp[i][j];//選択するしないの2通り } } } printf("%lld\n", dp[n][3]); return 0; }