Editorial for Cắt gỗ
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
#include <iostream> #include <algorithm> using namespace std; int value[51],a[51],n,g[51][51],f[51][101],ans; int main() { int x,y,m; cin >> n; for (int i=1;i<=n;i++) cin >> a[i]; cin >> m; while (m--) cin >> x >> y, value[x]=max(value[x],y); // precalc for each bar for (int i=1;i<=50;i++) g[i][0]=-1000000; for (int i=1;i<=50;i++) for (int j=1;j<=i;j++) for (int ii=0;ii<i;ii++) g[i][j]=max(g[i][j],g[ii][j-1]+value[i-ii]); // dp for (int i=1;i<=n;i++) for (int j=1;j<=a[i];j++) for (int k=j-1;k<=100;k++) f[i][k]=max(f[i][k],f[i-1][k-j+1]+g[a[i]][j]); for (int k=0;k<=100;k++) ans=max(ans,f[n][k]-k*(k+1)/2); cout << ans << endl; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> const int N = 53; const int lim = 73; using namespace std; int F[N][N][lim]; int res, n, m; int a[N], val[N]; void maximize(int &a, int b) {a = a > b ? a : b; res = res > a ? res : a;} int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; cin >> m; int d, v; for(int i = 1; i <= m; i++) { cin >> d >> v; val[d] = v; } memset(F, 255, sizeof F); F[1][a[1]][0] = 0; for(int i = 1; i <= n; i++) for(int j = a[i]; j; j--) for(int k = 0; k < lim - 1; k++) if (F[i][j][k] != -1) { for(int t = 1; t < j; t++) maximize(F[i][j - t][k + 1], F[i][j][k] + val[t] - k - 1); maximize(F[i + 1][a[i + 1]][k], F[i][j][k] + val[j]); } cout << res; return 0; }
Code mẫu của RR
{$R+,Q+} PROGRAM CATGO; CONST FINP=''; FOUT=''; max=52; VAR t,n,m:integer; gt:array[0..max] of longint; c:array[1..max] of longint; d:array[1..max,0..max*max] of longint; kq:array[0..max,0..max*max] of longint; procedure readInput; var f:text; u,i:integer; begin assign(f,FINP); reset(f); read(f,n); for i:=1 to n do read(f,c[i]); read(f,m); for i:=1 to m do begin read(f,u,gt[u]); d[u,0]:=gt[u]; end; close(f); end; function max2(a,b:longint):longint; begin if a>b then max2:=a else max2:=b; end; procedure writeOutput; var f:text; answer,i:longint; begin assign(f,FOUT); rewrite(f); answer:=0; for i:=0 to t do answer:=max2(answer,kq[n,i]); writeln(f,answer); close(f); end; procedure QHD1; var i,j,k:integer; begin for i:=1 to max do for j:=1 to i-1 do for k:=1 to i-1 do d[i,j]:=max2(d[i,j],d[k,j-1]+gt[i-k]); end; function min2(a,b:longint):longint; begin if a<b then min2:=a else min2:=b; end; procedure QHD2; var i,j,k,u,g,l,gg:integer; begin t:=0; for i:=1 to n do begin u:=c[i]; l:=t; t:=t+u-1; gg:=min2(t,max); for j:=0 to gg do begin g:=min2(l,j); g:=min2(max,g); for k:=0 to g do kq[i,j]:=max2(kq[i,j],kq[i-1,k]+d[u,j-k]+k*(k+1) div 2-j*(j+1) div 2); end; end; end; BEGIN readInput; QHD1; QHD2; writeOutput; END.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int n,m,kt[51],dai[51],gia[51]; int d[51][51],flag[51],f[51][53]; int main() { //freopen("CATGO_10.in","r",stdin); for(int i = 0;i<=50;i++) { flag[i]=0; for(int j = 0;j<=50;j++) { d[i][j]=0; f[i][j]=0; } } scanf("%d",&n); for(int i = 1;i<=n;i++) scanf("%d",&kt[i]); scanf("%d",&m); for(int i = 1;i<=m;i++) { scanf("%d %d",&dai[i],&gia[i]); flag[dai[i]]=i; } for(int i = 1;i<=50;i++) for(int j = 0;j<=50;j++) { if(j==0) { if( flag[i]!=0) d[i][j]=gia[flag[i]]; } else { int max=0; for(int k = 1;k<=i-1;k++) if(d[k][j-1]+d[i-k][0]>max) max = d[k][j-1]+d[i-k][0]; d[i][j]=max; } //if(i==10) printf("%d %d %d\n",j,d[i][j],flag[10]); } for(int i = 1;i<=n;i++) for(int j = 0;j<=52;j++) { if(i==1) f[i][j]=d[kt[i]][j]; else { int max = 0; for(int k = 0;k<=j;k++) if(f[i-1][k]+d[kt[i]][j-k]>max) max = f[i-1][k]+d[kt[i]][j-k]; f[i][j] = max; } } int Max = 0; for(int i=0;i<=52;i++) if(f[n][i]-i*(i+1)/2>Max) { Max = f[n][i]-i*(i+1)/2; // printf("%d %d %d\n",i,f[n][i],Max); } printf("%d",Max); //getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> typedef long long ll; using namespace std; int n,m; int g[52][52],f[52][502]; int a[52],len[52],val[52]; int main() { // freopen("catgo.in","r",stdin); // freopen("catgo.ou","w",stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &m); for (int i = 0; i < m; i++) scanf("%d %d", &len[i], &val[i]); memset(g,0,sizeof(g)); for (int i = 0; i < m; i++) g[len[i]][0] = max(g[len[i]][0],val[i]); for (int j = 1; j < 50; j++) for (int i = 1; i <= 50; i++) for (int t = 0; t < m; t++) if (i >= len[t]) g[i][j] = max(g[i][j],g[i - len[t]][j - 1] + val[t]); memset(f,0,sizeof(f)); for (int i = 1; i <= n; i++) for (int j = 0; j <= 500; j++) for (int t = 0; t < a[i] && t <= j; t++) f[i][j] = max(f[i][j],f[i - 1][j - t] + g[a[i]][t]); int best = 0; for (int i = 0; i <= 500; i++) best = max(best,f[n][i] - i * (i + 1) / 2); printf("%d\n", best); };
Code mẫu của khuc_tuan
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; ++i) a[i] = sc.nextInt(); int m = sc.nextInt(); int[] v = new int[55]; for (int i = 0; i < m; ++i) { int x = sc.nextInt(); v[x] = sc.nextInt(); } int[][] f = new int[55][55]; for (int i = 0; i < f.length; ++i) for (int j = 0; j < f[i].length; ++j) if (j == 0) f[i][j] = v[i]; else for (int len = 1; len < i; ++len) f[i][j] = Math.max(f[i][j], f[i - len][j - 1] + v[len]); int[][] g = new int[n][1000]; for (int i = 0; i < n; ++i) for (int j = 0; j < g[i].length; ++j) for (int t = 0; t < 55 && t <= j; ++t) g[i][j] = Math.max(g[i][j], (i == 0 ? 0 : g[i - 1][j - t]) + f[a[i]][t]); int total = 0; int res = 0; for (int x = 0; x < 1000; ++x) { total += x; res = Math.max(res, g[n - 1][x] - total); } System.out.println(res); } }
Comments