Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
using namespace std; const int maxn = 2002; const int INF = 1e9; vector
> graph[maxn]; int n; int dp[maxn][4100]; int rek(int at, int number) { if(at >= n) { return 0; } if(dp[at][number] != -1) { return dp[at][number]; } int res = INF; int idx = (int) (lower_bound(graph[at].begin(), graph[at].end(), make_pair(number, 0)) - graph[at].begin()); if(idx >= 0 and idx < graph[at].size()) { for(int i = idx; i < (int) graph[at].size(); i++) { int nxt_number = graph[at][i].first; int swaps = graph[at][i].second; res = min(res, rek(at + 1, nxt_number) + swaps); } } return dp[at][number] = res; } int main() { cin >> n; vector
v(n); for(int i = 0; i < n; i++) { cin >> v[i]; } for(int i = 0; i < n; i++) { for(int j = 0; j <= 4095; j++) { dp[i][j] = -1; if(__builtin_popcount(j) == __builtin_popcount(v[i])) { int swaps = __builtin_popcount(v[i] ^ j) / 2; graph[i].push_back(make_pair(j, swaps)); } } } cout << rek(0, 0) << endl; return 0; }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)