Editorial for The problem for kid
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 happyboy99x
#include<cstdio> #include<climits> const int N = 20; int f[1 << N], a[N][N], n; long long c[1 << N]; void enter() { scanf("%d", &n); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) scanf("%d", &a[i][j]); } int snoob(const int &x) { int r = x & -x, h = x + r; return h | (x ^ h) / r >> 2; } void solve() { const int Omega = 1 << n; f[0] = 0; c[0] = 1; for(int i = 0; i < n; ++i) for(int s = (1 << (i+1)) - 1; s < Omega; s = snoob(s)) { f[s] = INT_MIN; for(int p = 0; p < n; ++p) if(s & 1 << p) { const int ss = s & ~(1 << p); if(f[ss] + a[i][p] > f[s]) { f[s] = f[ss] + a[i][p]; c[s] = c[ss]; } else if(f[ss] + a[i][p] == f[s]) c[s] += c[ss]; } } printf("%d %lld\n", f[Omega - 1], c[Omega - 1]); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
program maugiao; uses math; const maxn=20; maxV=1 shl maxn; fi=''; var a:array[0..maxn,0..maxn] of longint; f:array[-1..maxV] of longint; way:array[0..maxV] of int64; n,m:longint; procedure input; var inp:text; i,j:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do begin for j:=1 to n do read(inp,a[i,j]); readln(inp); end; close(inp); end; function getbit(i,j:longint):boolean; begin exit((i shr (j-1) and 1)=1); end; procedure dp; var i,j,t,p:longint; begin way[0]:=1; for j:=1 to 1 shl n - 1 do begin t:=0; for i:=1 to n do if getbit(j,i) then inc(t); for i:=1 to n do if getbit(j,i) then begin p:=f[j-1 shl (i-1)]+a[t,i]; if f[j]<p then begin f[j]:=p; way[j]:=way[j-1 shl (i-1)]; end else if f[j]=p then way[j]:=way[j]+way[j-1 shl (i-1)]; end; end; end; begin input; dp; write(f[1 shl n-1],' ',way[1 shl n -1]); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #include <iomanip> #include <bitset> #include <complex> #define FOR(i,a,b) for(i = a; i <= b; ++i) #define REP(i,a) for(i = 0; i < a; ++i) #define MP make_pair #define PB push_back #define F first #define S second using namespace std; #define TWO(x) (1<<(x)) #define CONTAIN(S,x) (S & TWO(x)) ; int f[1100111], n, a[22][22]; long long g[1100111]; vector<int> ls[22]; int main() { int i, mask, j; scanf("%d", &n); FOR(i,1,n) FOR(j,1,n) scanf("%d", &a[i][j]); f[0] = 0; g[0] = 1; int cnt; REP(mask,TWO(n)) { cnt = 0; REP(i,n) if (CONTAIN(mask,i)) ++cnt; ls[cnt].PB(mask); } int cur, mask2, x, sz; FOR(i,0,n-1) { sz = ls[i].size(); REP(x,sz) { mask = ls[i][x]; if (!*(g+mask)) continue; REP(j,n) if (!CONTAIN(mask,j)) { cur = *(f+mask) + a[i+1][j+1]; mask2 = mask + TWO(j); if (cur > *(f+mask2)) { *(f+mask2) = cur; *(g+mask2) = *(g+mask); } else if (cur == *(f+mask2)) *(g+mask2) += *(g+mask); } } } cout << f[TWO(n)-1] << ' ' << g[TWO(n)-1] << endl; return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --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 Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, unsigned long long> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = { 0, 0, -1, +1 , -1, -1, +1, +1}; const int dc[] = { -1, +1, 0, 0 , -1, +1, -1, +1}; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const ll mod = (ll) 1e9 + 7; #define maxn 20 int n, a[maxn][maxn], u; II f[(1 << maxn)]; II comp(II P0, II P1){ if(P0.fi == P1.fi) return mp(P0.fi, P0.se + P1.se); if(P0.fi < P1.fi) return P1; else return P0; } int main() { // freopen("in.txt", "r", stdin); cin >> n; Rep(i, n) Rep(j, n) cin >> a[i][j]; f[0] = mp(0, 1); For(mask, 1, (1 << n) - 1){ u = cntbit(mask) - 1; Rep(i, n) if(getbit(mask, i)){ f[mask] = comp(f[mask], mp(f[offbit(mask, i)].fi + a[u][i], f[offbit(mask, i)].se)); } } // cout << f[1].fi << " " << f[1].se << endl; cout << f[(1 << n) - 1].fi << " " << f[(1 << n) - 1].se << endl; // cout << clock() << endl; return 0; }
Comments