https://www.acmicpc.net/problem/16319
16319번: Explosion Exploit
The first line of input contains the three integers n, m, and d (1 ≤ n, m ≤ 5, 1 ≤ d ≤ 100). Then follows a line containing n integers, the current health of all your minions. Finally, the third line contains m integers, the current health of all t
www.acmicpc.net
dp의 상태를 (7 ^ 5) * (7 ^ 5) 로 정의하면 터진다. 하지만 사실 미니언들의 순서는 무시할 수 있다. (오름차순으로 정렬한 상태로 생각)
즉, 상태의 개수는 (7H5) ^ 2 이다.
dp[7H5][7H5]로 할 수도 있지만 난 그냥 map을 써서 map<pair<vector<int>, vector<int>>, double> dp로 짰다.
코드
더보기
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define _unique(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
const int INF = 2e9;
const ll mod = 998244353;
const double eps = 1e-9;
int n, m, d;
int cnt1;
vector<int> a1, a2;
map<pair<vector<int>, vector<int>>, double> dp;
double dfs(vector<int> v1, vector<int> v2){
if(dp.contains({v1, v2})) return dp[{v1, v2}];
dp[{v1, v2}] = 0;
double &ret = dp[{v1, v2}];
ret = 0;
int cnt = 0;
for(auto i:v1) cnt+=i;
for(auto i:v2) cnt+=i;
if(d<(cnt1-cnt)) return ret;
int cnt3 = 0;
for(auto i:v2) cnt3+=i;
if(cnt3==0) return ret = 1;
int cnt2= 0;
for(auto i:v1) if(i) cnt2++;
for(auto i:v2) if(i) cnt2++;
for(int i=0;i<n;i++){
if(v1[i]==0) continue;
vector<int> tmp = v1;
tmp[i]--;
sort(all(tmp));
ret += (double)1/cnt2 * dfs(tmp, v2);
}
for(int i=0;i<m;i++){
if(v2[i]==0) continue;
vector<int> tmp = v2;
tmp[i]--;
sort(all(tmp));
ret += (double)1/cnt2 * dfs(v1, tmp);
}
return ret;
}
void solve() {
cin>>n>>m>>d;
a1.resize(n);
a2.resize(m);
for(auto &i:a1) {
cin>>i;
cnt1+=i;
}
for(auto &i:a2) {
cin>>i;
cnt1+=i;
}
sort(all(a1));
sort(all(a2));
cout<<dfs(a1, a2);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(10);
#ifndef ONLINE_JUDGE
freopen("./input.txt", "r", stdin);
clock_t _st_t = clock();
#endif
int tt = 1;
//cin>>tt;
while(tt--){
solve();
cout<<'\n';
}
#ifndef ONLINE_JUDGE
cerr << endl << endl << (double) (clock() - _st_t) / (double) CLOCKS_PER_SEC << "sec" << endl;
#endif
return 0;
}