- Quiz
- AC
- 補足
- 解説はeditorialの通り
- 部分和が実現できるか?のDPを関数化しておいた
- 計算量注意 O(N2)
// 部分和問題 subset sum // 部分和でtargetを作ることができるか?を返す // O(N^2) bool can_subset_sum(VI A, ll target){ ll N = SZ(A); vector<bool> dp(target+1); dp[0]=1; rep(i,N){ ll a = A[i]; for(int j=target; j>=0; j--){ // 状態jからaだけ足す if(dp[j]){ // そこからの遷移 ll to = j+a; if(to>target)continue; dp[to]=1; } } } return dp[target]; } // for codeforces void solve(){ ll N; cin>>N; N*=2; VI A(N); ll ma=0; VI I; rep(i, N){ cin >> A[i]; if(ma<A[i]){ I.push_back(i); ma = A[i]; } } I.push_back(N); VI L; rep(i,SZ(I)-1){ ll len = I[i+1]-I[i]; L.push_back(len); } if(can_subset_sum(L, N/2)){ p_yes(); }else{ p_no(); } } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; while(N--)solve(); return 0; }
部分和を実現するindexたちを復元するには?
部分和問題をdp[i][j] := (i個目までで総和をjにできるか)で解いて復元もしたいとき、各jについてdp[i][j]がtrueになる最小のiを、1次元のdpテーブルに埋めてくだけでいいのか。かしこ~
— りーふ@競プロ (@leaf_1415) November 3, 2020