Hướng dẫn giải của Dãy con dài nhất có tổng chia hết cho K


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.

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,k,t,j,p:longint;
    f:array[0..1,0..51] of longint;

begin
     readln(n,k);
     fillchar(f,sizeof(f),0);
     f[0,0]:=1;
     for i:=1 to n do
     begin
          p:=i mod 2;
          read(t);
          for j:=0 to k-1 do f[p,j]:=0;
          for j:=0 to k-1 do
              if (f[1-p,j]>0) then
              begin
                   if (f[p,j]<f[1-p,j]) then
                      f[p,j]:=f[1-p,j];
                   if (f[p,(j+t) mod k]<=f[1-p,j]) then
                      f[p,(j+t) mod k]:=f[1-p,j]+1;
              end;
     end;
     write(f[p,0]-1);
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 1005
#define KK 55

int f[N][KK], n, k, a[N];

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    LL s = 0;
    scanf("%d%d",&n,&k);
    fo(i,1,n) { scanf("%d",a+i); s = (s+a[i])%k; }
    //f[i][j], chon ra it nhat f[i][j] phan tu trong doan a[1..i] de co tong chia k du i
    f[0][0] = 0; fo(i,1,k-1) f[0][i] = INF;
    fo(i,1,n) rep(j,k)
        f[i][j] = min(f[i-1][j], f[i-1][((j-a[i])%k+k)%k]+1);
    printf("%d\n", n-f[n][s%k]);
    return 0;
}

Code mẫu của ladpro98

program qbseq;
uses    math;
const   fi='';
var     f:array[0..1001,0..51] of longint;
        a:array[1..1000] of longint;
        inp:text;
        n,i,k:longint;
        check:array[0..1001,0..51] of boolean;
procedure input;
var     i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,k);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);
end;

function qhd(i,t:longint):longint;

begin
        if check[i,t] then exit(f[i,t]);
        f[i,t]:=max(qhd(i-1,t),1+qhd(i-1,(t+k-(a[i] mod k)) mod k));
        check[i,t]:=true;
        exit(f[i,t]);
end;

begin
        input;
        f[0,0]:=0;
        check[0,0]:=true;
        for i:=1 to k-1 do
        begin
                f[0,i]:=low(integer);
                check[0,i]:=true;
        end;
        write(qhd(n,0));
end.

Code mẫu của RR

uses math;
var
  a:array[1..1011] of longint;
  f:array[1..1011,0..50] of longint;
  next,n,k,i,j:longint;
begin
  read(n,k);
  for i:=1 to n do read(a[i]);

  fillchar(f,sizeof(f),$FF);
  f[1,0]:=0;
  f[1,a[1] mod k]:=1;

  for i:=2 to n do
    begin
      for next:=0 to k-1 do
        f[i,next]:=f[i-1,next];

      for j:=0 to k-1 do
        if f[i-1,j]>=0 then
          begin
            next:=(j+a[i]) mod k;
            f[i,next]:=max(f[i,next],f[i-1,j]+1);
          end;
    end;

  writeln(f[n,0]);
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
main()
{ int n,k,a[1001],b[1001][51],m,l;
  long x=0;
  scanf("%d %d",&n,&k);
  for(int i=1;i<=n;i++)
  { scanf("%d",&a[i]);
    a[i]= a[i]%k ;
    x+=a[i];
  }
  m=x%k ;
  if(m==0)
    printf("%d",n);
  else
  {
  for(int i=0;i<k;i++)
    b[0][i]=1001;
  for(int i=1;i<=n;i++)
  { for(int j=0;j<k;j++)
    { if(j!=a[i])
      { l=j-a[i];
        if(l<0)
          l=l+k;
        if(b[i-1][l]+1>=b[i-1][j])
          b[i][j]=b[i-1][j];
        else b[i][j]=b[i-1][l]+1;
      }
      else  b[i][j]=1;
    }
  }
  printf("%d",n-b[n][m]);
  }
  //getch();
}

Code mẫu của ll931110

Program QBSEQ;
        Const
                input  = '';
                output = '';
                   max = 1000000000;
        Var
                a: array[1..1000] of longint;
                F: array[0..1000,0..1000] of longint;
              n,k: longint;

Procedure enter;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);
                                Readln(fi, n, k);
                                For i:= 1 to n do read(fi, a[i]);
                Close(fi);
          End;

Function sub(x,y: longint): longint;
         Var
                tmp: longint;
         Begin
                sub:= (x - y) mod k;
                If sub < 0 then sub:= sub + k;
         End;

Function min(x,y: longint): longint;
         Begin
                If x < y then exit(x) else exit(y);
         End;

Procedure optimize;
          Var
                i,t: longint;
          Begin
                F[0,0]:= 0;
                For t:= 1 to k - 1 do F[0,t]:= max;

                For i:= 1 to n do
                        For t:= 0 to k - 1 do
                                F[i,t]:= min(F[i - 1,t], F[i - 1, sub(t, a[i])] + 1);
          End;

Procedure solve;
          Var
                  fo: text;
               sum,i: longint;
          Begin
                sum:= 0;
                For i:= 1 to n do sum:= sum + a[i];

                Assign(fo, output);
                        Rewrite(fo);
                        Writeln(fo, n - F[n, sum mod k]);
                Close(fo);
          End;

Begin
        enter;
        optimize;
        solve;
End.

Code mẫu của skyvn97

#include<stdio.h>
int opt[2000][100];
int a[2000];
int n,k,i,j,s;
int f(int x)
{
    if (x>=0) return (x);
    return (x+k);
}
int min(int a,int b)
{
    if (a<b) return (a); else return (b);
}
int main(void)
{
    scanf("%d",&n);
    scanf("%d",&k);
    s=0;
    for (i=1;i<=n;i=i+1)
        {
         scanf("%d",&a[i]);
         a[i]=a[i]%k;
         s=(s+a[i])%k;
        }
    opt[0][0]=0;
    for (i=1;i<k;i=i+1) opt[0][i]=32000;
    for (i=1;i<=n;i=i+1)
        for (j=0;j<k;j=j+1)
            opt[i][j]=min(opt[i-1][j],opt[i-1][f(j-a[i])]+1);
    printf("%d",n-opt[n][s%k]);
    return 0;       
}

Code mẫu của khuc_tuan

#include <stdio.h>
#include <iostream>
#include <set>
using namespace std;

int n, k;
int f1[55], f2[55];

int main() {
    scanf("%d%d", &n, &k);
    int *f = f1, *q = f2;
    for(int i=0;i<55;++i) f1[i] = -1000000;
    f1[0] = 0;
    for(int i=0;i<n;++i) {
        int x; scanf("%d", &x);
        for(int j=0;j<55;++j) q[j] = -1000000;
        for(int du=0;du<k;++du) q[(du+x)%k] >?= (f[du]+1) >? (f[(du+x)%k]);
        swap( f, q);
    }
    printf("%d\n", f[0]);
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.