Editorial for Khuyến mãi


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

#include <iostream>
#include <algorithm>
#define oo 100000000
using namespace std;

int f[1010][1010],n,x;

int main()
{
    cin >> n;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            f[i][j]=oo;
    f[0][0]=0;
    for (int i=0;i<n;i++) 
    {
        cin >> x;
        for (int j=0;j<=i;j++)
            if (f[i][j]!=oo)
            {
                f[i+1][j+(x>100)]=min(f[i+1][j+(x>100)],f[i][j]+x);
                if (j) f[i+1][j-1]=min(f[i+1][j-1],f[i][j]);
            }
    }
    int ans=oo;
    for (int j=0;j<=n;j++) ans=min(ans,f[n][j]);
    cout << ans << endl;
}

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
#include<climits>
using namespace std;

#define N 1002
int f[N][N], a[N], n;

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

Code mẫu của ladpro98

uses    math;
const   maxn=1111;
        fi='';
        oo=trunc(1e9);
var     inp:text;
        n,i,j,res:longint;
        a:array[0..maxn] of longint;
        f:array[0..maxn,0..maxn] of longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n);
        for i:=1 to n do readln(inp,a[i]);
        for j:=1 to n+1 do f[0,j]:=oo;
        for i:=1 to n do begin
                f[i,0]:=min(f[i-1,1],f[i-1,0]+a[i]);
                for j:=1 to i do
                if a[i]>100 then f[i,j]:=min(f[i-1,j+1],f[i-1,j-1]+a[i])
                else    f[i,j]:=min(f[i-1,j+1],f[i-1,j]+a[i]);
                for j:=i+1 to n+1 do f[i,j]:=oo;
        end;
        res:=oo;
        for i:=0 to n do res:=min(res,f[n,i]);
        write(res);
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(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

int n, a[1011], f[1011][1011];

void up(int &a, int b) {
    if (b < 0) return ;
    if (a < 0) a = b;
    else a = min(a, b);
}

int main() {
    scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
    memset(f, -1, sizeof f);
    f[0][0] = 0;
    FOR(i,0,n-1) FOR(j,0,i) if (f[i][j] >= 0) {
        if (j > 0) {
            up(f[i+1][j-1], f[i][j]);
        }
        up(f[i+1][j + (a[i+1] > 100 ? 1 : 0)], f[i][j] + a[i+1]);
    }

    int res = 1000111000;
    FOR(j,0,n) up(res, f[n][j]);
    cout << res << endl;
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1000
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n, f[maxn + 5][maxn + 5], a;

int main(){

   // freopen("input.in","r",stdin);
   // freopen("output.out","w",stdout);
    scanf("%d",&n);
    for(int i = 0; i <= n+2; i++) for(int j = 0; j <= n+2; j++) f[i][j] = oo;
    f[0][0] = 0;
    int kq = oo;
    if(n == 0) kq = 0;
    for(int i = 1; i <= n; i++){
        scanf("%d",&a);
        for(int j = 0; j <= i; j++){
            f[i][j] = min(f[i][j],f[i-1][j+1]);
            if(a > 100){
                if(j > 0) f[i][j] = min(f[i][j], f[i-1][j-1] + a);
            }
            else f[i][j] = min(f[i][j],f[i-1][j] + a);
            if( i == n) kq = min(kq, f[i][j]);
        }
    }
    printf("%d",kq);
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.