fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. void in(int **f, int n, int k)
  7. {
  8.     cout << " n/t";
  9.     for (int i = 0; i < k; i++)
  10.     {
  11.         printf("%4d", i);
  12.     }
  13.     cout << endl;
  14.     for (int i = 0; i <= n; i++)
  15.     {
  16.         printf("%4d", i);
  17.         for (int t = 0; t < k; t++)
  18.         {
  19.             if (f[i][t] == INT_MAX)
  20.             {
  21.                 cout << " +00";
  22.             }
  23.             else
  24.             {
  25.                 printf("%4d", f[i][t]);
  26.             }
  27.         }
  28.         cout << endl;
  29.     }
  30. }
  31.  
  32. int sub(int x, int y, int k)
  33. {
  34.     int tmp = (x - y) % k;
  35.     return tmp >= 0 ? tmp : tmp + k;
  36. }
  37.  
  38. int main()
  39. {
  40.     int n, k, sum = 0;
  41.     cin >> n >> k;
  42.     int A[n];
  43.     for (int i = 0; i < n; i++)
  44.     {
  45.         cin >> A[i];
  46.         sum += A[i];
  47.     }
  48.     if (sum % k == 0)
  49.     {
  50.         cout << "Day da cho thoa man yeu cau." << endl
  51.              << "Tong =" << sum;
  52.         return 0;
  53.     }
  54.     int **f = new int *[n + 1];
  55.     for (int i = 0; i < n + 1; i++)
  56.     {
  57.         f[i] = new int[k];
  58.     }
  59.     // optimize
  60.     f[0][0] = 0;
  61.     for (int t = 1; t < k; t++)
  62.         f[0][t] = INT_MAX;
  63.     for (int i = 1; i <= n; i++)
  64.     {
  65.         for (int t = 1; t < k; t++)
  66.         {
  67.             if (f[i - 1][t] < f[i - 1][sub(t, A[i - 1], k)] + 1)
  68.                 f[i][t] = f[i - 1][t];
  69.             else
  70.                 f[i][t] = f[i - 1][sub(t, A[i - 1], k)] + 1;
  71.         }
  72.     }
  73.     in(f, n, k);
  74.     cout << "Chieu dai day con: " << n - f[n][sum % k] << endl;
  75.     // truy vet
  76.     int t = sum % k;
  77.     sum = 0;
  78.     for (int i = n; i >= 1; i--)
  79.     {
  80.         if (f[i][t] == f[i - 1][t])
  81.         {
  82.             printf("a[%d]=%d;", i, A[i - 1]);
  83.             sum += A[i - 1];
  84.         }
  85.         else
  86.         {
  87.             t = sub(t, A[i - 1], k);
  88.         }
  89.     }
  90.     cout << endl
  91.          << "Tong =" << sum;
  92.     return 0;
  93. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
6 5
1 2 3 4 9 10 5 6 7
stdout
copy 
 n/t   0   1   2   3   4
   0   0 +00 +00 +00 +00
   1   0   1 +00 +00 +00
   2   0   1   1   2 +00
   3   0   1   1   1   2
   4   0   1   1   1   1
   5   0   1   1   1   1
   6   0   1   1   1   1
Chieu dai day con: 5
a[6]=10;a[5]=9;a[3]=3;a[2]=2;a[1]=1;
Tong =25
https://ideone.com/gr7ifQ
language:
C++ (gcc 8.3)
created:
111 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!