Hướng dẫn giải của Thảm kịch ở nông trang
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=1000; MAXK=30; var f1,f2:text; n,m,k:longint; x,y:array[1..MAXN] of longint; dd:array[1..MAXN,1..MAXN] of byte; d:array[1..MAXK,-MAXK..MAXK,-MAXK..MAXK] of longint; trace:array[1..MAXK,-MAXK..MAXK,-MAXK..MAXK] of char; count:array[-MAXK..MAXK,-MAXK..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 u,v:longint; begin read(f1,n,m,k); inc(k); for n:=1 to n do read(f1,y[n],x[n]); for m:=1 to m do begin read(f1,v,u); dd[u,v]:=1; end; end; procedure solve; var c,di,dj,i,u,v,time,temp:longint; begin for di:=-k to k do for dj:=-k to k do begin c:=0; for i:=1 to n do begin u:=x[i]+di; v:=y[i]+dj; if (u>0) and (v>0) and (u<=1000) and (v<=1000) and (dd[u,v]=1) then inc(c); end; count[di,dj]:=c; end; for di:=-k to k do for dj:=-k to k do d[k,di,dj]:=count[di,dj]; for time:=k-1 downto 1 do for di:=-time to time do for dj:=-time to time do begin //update E d[time,di,dj]:=d[time+1,di,dj+1]+count[di,dj]; trace[time,di,dj]:='E'; //update N temp:=d[time+1,di+1,dj]+count[di,dj]; if temp>d[time,di,dj] then begin d[time,di,dj]:=temp; trace[time,di,dj]:='N'; end; //update S temp:=d[time+1,di-1,dj]+count[di,dj]; if temp>d[time,di,dj] then begin d[time,di,dj]:=temp; trace[time,di,dj]:='S'; end; //update W temp:=d[time+1,di,dj-1]+count[di,dj]; if temp>d[time,di,dj] then begin d[time,di,dj]:=temp; trace[time,di,dj]:='W'; end; end; end; procedure ans; var time,u,v:longint; ch:char; begin writeln(f2,d[1,0,0]); u:=0; v:=0; for time:=1 to k-1 do begin ch:=trace[time,u,v]; write(f2,ch); case ch of 'E': inc(v); 'S': dec(u); 'N': inc(u); 'W': dec(v); end; end; end; begin openF; inp; solve; ans; closeF; end.
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> #include <cassert> 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, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = {+1, +0, +0, -1}; const int dc[] = {+0, +1, -1, +0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; //const ll mod = (ll)1e9 + 7; #define maxn 70 string str = "ENSW"; int d[maxn][maxn], a[1005][1005], f[maxn][maxn][33]; string s[maxn][maxn][33]; int n, m, k; int x[1005], y[1005]; bool namtrong(int u, int v){ return(u >= 0 && u <= 1000 && v >= 0 && v <= 1000); } int main(){ // freopen("in.txt", "r", stdin); cin >> n >> m >> k; ms(a, 0); For(i, 1, n){ scanf("%d %d", &x[i], &y[i]); } int u, v; For(i, 1, m){ scanf("%d %d", &u, &v); a[u][v]++; } For(i, 0, 66) For(j, 0, 66){ d[i][j] = 0; For(run, 1, n){ u = x[run] + i - 33; v = y[run] + j - 33; if(namtrong(u, v)) d[i][j] += a[u][v]; } } ms(f, -0x3f); f[33][33][0] = 0; For(run, 0, k - 1){ For(i, 1, 64) For(j, 1, 64){ Rep(h, 4){ u = i + dr[h]; v = j + dc[h]; string m = s[i][j][run]; m.pb(str[h]); if(f[u][v][run + 1] < f[i][j][run] + d[u][v] || (f[u][v][run + 1] == f[i][j][run] + d[u][v] && s[u][v][run + 1].compare(m) > 0)){ f[u][v][run + 1] = f[i][j][run] + d[u][v]; s[u][v][run + 1] = m; } } } } int MAX = -1; string S; For(i, 0, 66) For(j, 0, 66) { if(MAX < f[i][j][k]){ MAX = f[i][j][k]; S = s[i][j][k]; } else if(MAX == f[i][j][k] && S.compare(s[i][j][k]) > 0){ MAX = f[i][j][k]; S = s[i][j][k]; } } cout << MAX << endl; cout << S << endl; // cout << clock() << endl; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> using namespace std; int dx[4] = {1,0,0,-1}; int dy[4] = {0,1,-1,0}; char ch[4] = {'E','N','S','W'}; int n,m,k; bool a[1032][1032]; int f[62][62][32]; int sx[1032],sy[1032]; char fin[32]; int rec(int ax,int ay,int t) { if (f[ax][ay][t] > -1) return f[ax][ay][t]; if (!t) { f[ax][ay][t] = 0; return 0; }; int best = 0; for (int i = 0; i < 4; i++) { int fx = ax + dx[i],fy = ay + dy[i]; int tmp = 0; for (int j = 0; j < n; j++) if (a[sx[j] + fx][sy[j] + fy]) tmp++; best = max(best,tmp + rec(fx,fy,t - 1)); }; f[ax][ay][t] = best; return best; }; void track(int ax,int ay,int t) { if (!t) return; int best = -1,pos = 0; for (int i = 0; i < 4; i++) { int fx = ax + dx[i]; int fy = ay + dy[i]; int tmp = 0; for (int j = 0; j < n; j++) if (a[sx[j] + fx][sy[j] + fy]) tmp++; if (best < rec(fx,fy,t - 1) + tmp) { best = rec(fx,fy,t - 1) + tmp; pos = i; }; }; fin[t] = ch[pos]; track(ax + dx[pos],ay + dy[pos],t - 1); }; int main() { // freopen("crisis.9.in","r",stdin); // freopen("cri.ou","w",stdout); scanf("%d %d %d", &n, &m, &k); memset(a,false,sizeof(a)); for (int i = 0; i < n; i++) scanf("%d %d", &sx[i], &sy[i]); for (int i = 0; i < m; i++) { int x,y; scanf("%d %d", &x, &y); a[x + 30][y + 30] = true; }; // cout << endl; // for (int i = 0; i < n; i++) cout << sx[i] + 33 << ' ' << sy[i] + 30 << endl; memset(f,-1,sizeof(f)); printf("%d\n", rec(30,30,k)); track(30,30,k); for (int i = k; i > 0; i--) printf("%c", fin[i]); //checking /* int ret = 0,ax = 30,ay = 30; for (int i = k; i > 0; i--) { int tmp = 0,move = -1; switch (fin[i]) { case 'E': move = 0; break; case 'N': move = 1; break; case 'S': move = 2; break; case 'W': move = 3; break; }; ax += dx[move]; ay += dy[move]; for (int j = 0; j < n; j++) if (a[sx[j] + ax][sy[j] + ay]) tmp++; ret += tmp; }; cout << ret << endl;*/ };
Bình luận