Editorial for Đi xem phim


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.

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

var n,i,j,re,c,s:longint;
    a:array[1..16] of longint;
begin
     read(c,n);
     for i:=1 to n do read(a[i]);
     for i:=1 to 1 shl n-1 do
     begin
           s:=0;
           for j:=1 to n do
                if i shr (j-1) and 1=1 then s:=s+a[j];
           if (s<=c) and (s>re) then re:=s;
           if re=c then break;
     end;
     writeln(re);
end.

Code mẫu của happyboy99x

#include <cstdio>

int f[20][5005];
int n, c;
int w[20];

int max( int a, int b ) {
    return a > b ? a : b;
}

int main() {
    scanf( "%d%d", &c, &n );
    for( int i = 0; i < n; ++i ) scanf( "%d", w+i );
    for( int i = 0; i <= n; ++i )
        for( int j = 0; j <= c; ++j )
            if ( i == 0 || j == 0 ) f[i][j] = 0;
            else f[i][j] = max( f[i-1][j], j >= w[i-1] ? w[i-1] + f[i-1][j-w[i-1]] : 0 );
    printf( "%d\n", f[n][c] );
    return 0;
}

Code mẫu của ladpro98

program vcowflix;
uses    math;
const   fi='';
var     a:array[1..16] of longint;
        c,n,res:longint;

procedure input;
var     inp:text;
        i:longint;

begin
        assign(inp,fi);
        reset(inp);
        readln(inp,c,n);
        for i:=1 to n do readln(inp,a[i]);
        close(inp);
end;

procedure duyet(tong,i:longint);
var     j:longint;
begin
        if (tong>c) or (i>n) then exit;
        res:=max(res,tong);
        for j:=i+1 to n do
        duyet(tong+a[j],j);
end;

procedure swap(i,j:longint);
var     t:longint;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(i,j:longint);
var     pivot:longint;
        l,r:longint;
begin
        if l>= r then exit;
        l:=i;r:=j;
        pivot:=a[random(r-l+1)+l];
        repeat
                while a[l]>pivot do inc(l);
                while a[r]<pivot do dec(r);
                if l<=r then
                begin
                        if l<r then swap(l,r);
                        inc(l);
                        dec(r);
                end;
        until l>r;

        sort(i,r);
        sort(l,j);

end;

begin
        input;
        sort(1,n);
        duyet(0,0);
        write(res);
end.

Code mẫu của RR

uses math;
var
  a:array[1..20] of longint;
  gh,sum,res,mask,i,n:longint;
begin
  read(gh,n);
  for i:=1 to n do read(a[i]);
  for mask:=0 to 1 shl n-1 do
    begin
      sum:=0;
      for i:=1 to n do
        begin
          if (mask shr (i-1)) and 1=1 then inc(sum,a[i]);
          if sum<=gh then res:=max(res,sum);
        end;
    end;

  writeln(res);
end.

Code mẫu của hieult

#include <iostream.h>
//#include <conio.h>
int sum, result, C, N;
int A[17]; 
using namespace std;
int dequy(int i)
{
   int j;
   sum=sum+A[i];
   if (sum<=C)
      {
              if (result<sum) result=sum;
              for (j=i+1; j<=N; j++) dequy(j);
      }        
   sum=sum-A[i]; 
}               
main ()
{
  int i;    
  cin>>C; cin>>N; 
  for (i=1; i<=N; i++) cin>>A[i];
  result=sum=0;
  A[0]=0;
  dequy(0);
  cout<<result;
  //getch();
}

Code mẫu của ll931110

Program VCOWFLIX;
        Const
                Input  = '';
                Output = '';
        Var
                a: array[1..16] of integer;
                b: array[0..5000] of integer;
              c,n: integer;

Procedure enter;
          Var
                f: text;
                i: integer;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, c, n);
                        For i:= 1 to n do readln(f, a[i]);
                Close(f);
          End;

Procedure optimize;
          Var
                t,i,k: integer;
                    f: text;
          Begin
                For i:= 1 to c do b[i]:= 1000;
                b[0]:= 0;

                For i:= 1 to c do
                    Begin
                        k:= 1;
                        While ((a[k] > i) or (b[i - a[k]] >= k))
                                              and (k <= n) do inc(k);
                        If k <= n then b[i]:= k;
                    End;

                t:= c;
                While b[t] = 1000 do dec(t);

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, t);
                Close(f);
          End;

Begin
        enter;
        optimize;
End.

Code mẫu của skyvn97

#include<stdio.h>
#include<vector>
#define MAX   22
using namespace std;
int a[MAX];
bool f[5005];
vector<int> v;
int n,c,i,j,s,r;
int main(void) {
    scanf("%d",&c);
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
    v.clear();
    for (i=1;i<=5000;i=i+1) f[i]=false;
    f[0]=true;
    v.push_back(0);
    for (i=1;i<=n;i=i+1) {
        s=v.size();
        for (j=0;j<s;j=j+1) {
            if (v[j]+a[i]>c) continue;
            if (!f[v[j]+a[i]]) {
                f[v[j]+a[i]]=true;
                v.push_back(v[j]+a[i]);
            }
        }           
    }       
    r=0;
    for (i=0;i<v.size();i=i+1)
        if ((v[i]<=c) && (v[i]>r)) r=v[i];
    printf("%d",r);
    return 0;
}

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 a = sc.nextInt();
        int n = sc.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; ++i)
            w[i] = sc.nextInt();
        int result = 0;
        for (int i = 0; i < (1 << n); ++i) {
            int total = 0;
            for (int j = 0; j < n; ++j)
                if ((i & (1 << j)) != 0)
                    total += w[j];
            if (total <= a)
                result = Math.max(result, total);
        }
        System.out.println(result);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.