Editorial for Sắp xếp các viên bi
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=20000; var n,re,m,s,u:longint; a:array[1..maxn] of longint; f,dem:array[1..maxn,1..10] of longint; sum:array[1..10,0..1023] of longint; b,d:array[1..10] of longint; procedure rf; var i,x,y,j:longint; begin read(n,m); read(a[1]); inc(d[a[1]]); for i:=2 to n do begin read(a[i]); dem[i]:=dem[i-1]; dem[i,a[i-1]]:=dem[i,a[i-1]]+1; inc(d[a[i]]); end; for i:=1 to n do for j:=1 to m do f[a[i],j]:=f[a[i],j]+dem[i,j]; for i:=1 to m do f[i,i]:=0; for i:=1 to m do for x:=1 to 1 shl m-1 do for j:=0 to m-1 do if (x shr j) and 1=1 then sum[i,x]:=sum[i,x]+f[i,j+1]; end; procedure att(i:longint); var j:longint; begin if i>m then begin if s<re then re:=s; exit; end; for j:=1 to m do if b[j]=0 then begin b[j]:=1; s:=s+sum[j,u]; u:=u+1 shl (j-1); if s<re then att(i+1); b[j]:=0; u:=u-1 shl (j-1); s:=s-sum[j,u]; end; end; procedure pr; var i,j,min,x:longint; begin re:=n*(n-1) div 2; s:=0; u:=0; att(1); end; procedure wf; begin writeln(re); end; begin rf; pr; wf; end.
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 20002; const int K = 11; using namespace std; int a[N], F[K][K], cnt[K]; int dp[1 << K]; int n, k; void minimize(int &a, int b) {a = a > b ? b : a;} int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> k; FOR(i, 0, n) { cin >> a[i]; a[i]--; FOR(j, 0, k) if (j != a[i]) F[a[i]][j] += cnt[j]; cnt[a[i]]++; } FOR(i, 1, 1 << k) dp[i] = INT_MAX; FOR(i, 0, 1 << k) { FOR(j, 0, k) { if ((i & (1 << j)) == 0) { int cost = 0; FOR(t, 0, k) if (i & (1 << t)) cost += F[t][j]; minimize(dp[i | (1 << j)], dp[i] + cost); } } } cout << dp[(1 << k) - 1]; return 0; }
Code mẫu của RR
//Written by Nguyen Thanh Trung {$R+,Q+} {$Mode objFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 20111; MAXK = 10; oo = 1000111000; var f1,f2 : text; n,k : longint; d : array[1..MAXK,1..MAXK] of longint; f : array[0..1 shl MAXK] of longint; a,right : array[1..MAXN] of longint; dd : array[1..MAXK] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,k); for i:=1 to n do read(f1,a[i]); end; function get(color:longint):longint; inline; var i,kq:longint; begin kq:=0; for i:=1 to k do if dd[i]=0 then kq+=d[i,color]; exit(kq); end; procedure solve; var i,ii,color,j,jj:longint; begin for color:=1 to k do begin for i:=n downto 1 do if a[i]=color then right[i]:=right[i+1]+1 else right[i]:=right[i+1]; for i:=1 to n do if a[i]<>color then d[a[i],color]+=right[i]; end; for i:=1 to 1<<k-1 do f[i]:=oo; for i:=0 to 1<<k-2 do begin fillchar(dd,sizeof(dd),0); for j:=1 to k do if (i>>(j-1)) and 1=1 then dd[j]:=1; for color:=1 to k do if (i>>(color-1)) and 1=0 then begin ii:=i+1<<(color-1); f[ii]:=min(f[ii],f[i]+get(color)); end; end; writeln(f2,f[1<<k-1]); end; begin openF; inp; solve; closeF; end.
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<sstream> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.00001 #define oo 111111111 #define mod 790972 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) #define MS(a, x) memset(a, x, sizeof(a)) #define SZ(a) (int)(a.size()) #define maxn 505 //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; int dx[] = {+1, 0, -1, 0}; int dy[] = {0, -1, 0, +1}; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } int num[11] = {0}, f[11][11] = {0}, x; int n, k; long long d[1 << 10] = {0}; int main(){ // OPEN(); scanf("%d %d", &n, &k); rep(i, n){ scanf("%d", &x); x --; rep(j, k) f[x][j] += num[j]; num[x]++; } FOR(i, 1, (1 << k) - 1){ d[i] = 1ll << 60; rep(j, 10) if((i >> j) & 1){ long long tang = 0; rep(k, 10) if(!((i >> k) & 1)) tang += f[j][k]; d[i] = min(d[i], tang + d[i - (1 << j)]); } } cout << d[(1 << k) - 1]; }
Comments