Editorial for Chặt cây
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 fi=''; fo=''; maxn=2000; max=100000000; var n:longint; a:array[0..maxn] of longint; f,k:array[1..maxn,1..maxn] of longint; procedure rf; var i,t:longint; begin assign(input,fi); reset(input); readln(n); a[0]:=0; for i:=1 to n do begin read(t); a[i]:=a[i-1]+t; end; close(input); end; procedure pr; var i,j,l,t,u:longint; begin for i:=1 to n do for j:=i+1 to n do begin f[i,j]:=max; f[j,i]:=f[i,j]; end; for i:=1 to n do k[i,i]:=i; for l:=2 to n do for i:=1 to n-l+1 do begin j:=i+l-1; for t:=k[i,j-1] to k[i+1,j] do begin u:=a[j]-a[i-1]+f[i,t-1]+f[t,j]; if u<f[i,j] then begin f[i,j]:=u; k[i,j]:=t; end; end; end; end; procedure wf; begin assign(output,fo); rewrite(output); write(f[1,n]); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include<cstdio> const int N = 2e3+1, INF = 1e9; int a[N], s[N], f[N][N], p[N][N], n; void enter() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); s[i] = s[i-1] + a[i]; } } void solve() { for(int i = 1; i <= n; ++i) f[i][i] = 0, p[i][i] = i; for(int l = 2; l <= n; ++l) for(int i = 1, j = i + l - 1; j <= n; ++i, ++j) { f[i][j] = INF; for(int t = p[i+1][j]; t >= p[i][j-1]; --t) if(s[j] - s[i-1] + f[i][t-1] + f[t][j] < f[i][j]) { f[i][j] = s[j] - s[i-1] + f[i][t-1] + f[t][j]; p[i][j] = t; } } printf("%d\n", f[1][n]); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 2002; const int oo = 2000000009; using namespace std; int a[N], sum[N]; int F[N][N], P[N][N]; int n; int main() { scanf("%d", &n); int i, j, k, new_F; for(i=1; i<=n; i++) { scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i]; } for(i=1; i<=n; i++) P[i][i] = i - 1; for(int len = 1; len <= n; len++) for(i = 1; i <= n - len; i++) { j = i + len; F[i][j] = oo; for(k = P[i][j - 1]; k <= P[i + 1][j]; k++) { //for(k=i; k<j; k++) { new_F = F[i][k] + F[k + 1][j]; if (F[i][j] > new_F) { F[i][j] = new_F; P[i][j] = k; } } F[i][j] += sum[j] - sum[i - 1]; } cout << F[1][n]; return 0; }
Code mẫu của RR
// http://codeforces.com/blog/entry/8219 // Original Recurrence: // dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j] for k = i+1..j-1 // Necessary & Sufficient Conditions: // A[i][j-1] <= A[i][j] <= A[i+1][j] // with A[i][j] = smallest k that gives optimal answer // Also applicable if the following conditions are met: // 1. C[a][c] + C[b][d] <= C[a][d] + C[b][c] (quadrangle inequality) // 2. C[b][c] <= C[a][d] (monotonicity) // for all a <= b <= c <= d // To use: // Calculate dp[i][i] and A[i][i] // // FOR(len = 1..n-1) // FOR(i = 1..n-len) { // j = i + len // FOR(k = A[i][j-1]..A[i+1][j]) // update(dp[i][j]) // } // OPTCUT #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 <complex> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) using namespace std; const int MN = 2011; int a[MN], dp[MN][MN], C[MN][MN], A[MN][MN]; int n; int main() { while (cin >> n) { FOR(i,1,n) { cin >> a[i]; a[i] += a[i-1]; } FOR(i,1,n) FOR(j,i,n) C[i][j] = a[j] - a[i-1]; FOR(i,1,n) dp[i][i] = 0, A[i][i] = i; FOR(len,1,n-1) FOR(i,1,n-len) { int j = i + len; dp[i][j] = 2000111000; FOR(k,A[i][j-1],A[i+1][j]) { int cur = dp[i][k-1] + dp[k][j] + C[i][j]; if (cur < dp[i][j]) { dp[i][j] = cur; A[i][j] = k; } } } cout << dp[1][n] << endl; } }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> main() { long cat[2001][2001],n,a[2001],tong[2001][2001],f[2001][2001],min; scanf("%ld",&n); for(long i=1;i<=n;i++) scanf("%ld",&a[i]); for(long i=1;i<=n;i++) for(long j=i;j<=n;j++) { if(i==j) tong[i][j]=a[i]; else tong[i][j]=tong[i][j-1]+a[j]; } for(long i=1;i<=n;i++) { f[i][i]=0; cat[i][i]=i; if(i!=n) { f[i][i+1]=tong[i][i+1]; cat[i][i+1]=i; } } for(long i=3;i<=n;i++) for(long j=1;j<=n-i+1;j++) { min=2000000000; //if(j==1&&i==3) //printf("%ld %ld\n",/*f[j][2]+f[3][j+i-1]*/f[j][1],f[2][3]); for(long k=cat[j][j+i-2];k<=cat[j+1][j+i-1];k++) { //printf("%lld\n",f[j][k]+f[k+1][j+i-1]); if(min>f[j][k]+f[k+1][j+i-1]) { min= f[j][k]+f[k+1][j+i-1]; cat[j][j+i-1]=k; } } f[j][j+i-1]=min+tong[j][j+i-1]; //printf("%ld %ld %ld %lld\n",i,j,cat[j][j+i-1],f[j][j+i-1]); } printf("%lld",f[1][n]); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program OPTCUT3; Const input = ''; output = ''; maxn = 2000; maxv = 500000000; Var a: array[1..maxn] of integer; k,f,w: array[1..maxn,1..maxn] of integer; n: integer; Procedure init; Var fi: text; i: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, n); For i:= 1 to n do read(fi, a[i]); Close(fi); End; Procedure gens; Var i,j: integer; Begin For i:= 1 to n do For j:= 1 to n do F[i,j]:= maxv; For i:= 1 to n do w[i,i]:= a[i]; For i:= 1 to n - 1 do For j:= i + 1 to n do w[i,j]:= w[i,j - 1] + a[j]; End; Procedure solve; Var l,i,j,t,v: integer; Begin For i:= 1 to n do Begin F[i,i]:= 0; k[i,i]:= i; End; For l:= 2 to n do For i:= 1 to n - l + 1 do Begin j:= i + l - 1; For t:= k[i,j - 1] to k[i + 1,j] do if t <> 1 then Begin v:= w[i,j] + f[i,t - 1] + f[t,j]; If f[i,j] > v then Begin f[i,j]:= v; k[i,j]:= t; End; End; End; End; Procedure printresult; Var fo: text; Begin Assign(fo, output); Rewrite(fo); Writeln(fo, F[1,n]); Close(fo); End; Begin init; gens; solve; printresult; End.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 2020 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) const int INF=(int)1e9+7; int f[MAX][MAX],t[MAX][MAX]; int a[MAX],s[MAX]; int n; void init(void) { scanf("%d",&n); FOR(i,1,n) { scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } } int sum(int l,int r) { return (s[r]-s[l-1]); } void optimize(void) { FOR(i,1,n-1) { f[i][i+1]=sum(i,i+1); t[i][i+1]=i; } FOR(i,3,n) FOR(j,1,n-i+1) { int l=j; int r=j+i-1; f[l][r]=INF; FOR(k,t[l][r-1],t[l+1][r]) if (f[l][r]>f[l][k]+f[k+1][r]) { f[l][r]=f[l][k]+f[k+1][r]; t[l][r]=k; } f[l][r]+=sum(l,r); } printf("%d",f[1][n]); } int main(void) { init(); optimize(); return 0; }
Code mẫu của khuc_tuan
//{$Q+,R+,S+} // {$APPTYPE CONSOLE} {$mode delphi} uses math; var i, j, k, n : integer; a : array[0..2000] of integer; t, F : array[0..2000,0..2000] of integer; begin read(n); for i:=1 to n do begin read(a[i]); inc(a[i], a[i-1]); end; for i:=n downto 1 do begin t[i,i] := i; for j:=i+1 to n do begin F[i,j] := 1000000000; for k:= t[i,j-1] to t[i+1,j] do if k < j then begin if F[i,j] > F[i,k] + F[k+1,j] then begin F[i,j] := F[i,k] + F[k+1,j]; t[i,j] := k; end; end; inc( F[i,j], a[j] - a[i-1]); end; end; writeln( F[1,n]); end.
Comments