fork download
copy 
  1. /*
  2.     Author: Loc Thien Vo
  3.     From: Ben Tre, Viet Nam
  4.     Organization: Ben Tre High School for Gifted Students (HSGS Ben Tre) | M-IT_CBT_23-26
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define    NAME                "message"
  11. #define    FastIO              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12.  
  13. void setData() {
  14.     FastIO
  15.     if(fopen(NAME ".INP", "r")) {
  16.         freopen(NAME ".INP", "r", stdin);
  17.         freopen(NAME ".OUT", "w", stdout);
  18.     }
  19. }
  20.  
  21. /*
  22.     My Solution: Dynamic Programming
  23. */
  24.  
  25. const int        N              = (int)5e2 + 5;
  26. const int        M              = (int)5e2 + 5;
  27. const int        INT_INF        = (int)1e9 + 7;
  28. const long long  LL_INF         = (long long)1e18 + 7;
  29. const int        MOD[3]         = {(int)1e9 + 7, (int)1e9 + 2277, (int)1e9 + 5277};
  30.  
  31. int numPack, numChannel;
  32. long long cost[N][M];
  33.  
  34. long long F[N][M]; // F[i][j]: Chi phi chuyen i goi tin dau tien tren j mang dau tien
  35. int tr[N][M]; // tr[i][j]: So goi dung tren kenh j de chuyen duoc i goi tin dau tien
  36.  
  37. int res[M]; // res[j]: So goi dung tren kenh j trong cach chuyen toi uu nhat (dap an bai toan)
  38.  
  39. void read() {
  40.     cin >> numPack >> numChannel;
  41.     for(int i = 1; i <= numPack; ++i)
  42. 		for(int j = 1; j <= numChannel; ++j) cin >> cost[i][j];
  43. }
  44.  
  45. long long dp() {
  46.     // BTCS
  47.     for(int i = 0; i <= numPack; ++i) F[i][0] = 0LL;
  48.     for(int j = 0; j <= numChannel; ++j) F[0][j] = 0LL;
  49.     for(int i = 1; i <= numPack; ++i) F[i][1] = cost[i][1], tr[i][1] = i;
  50.  
  51.     // CTTH
  52.     for(int i = 1; i <= numPack; ++i) {
  53. 		for(int j = 2; j <= numChannel; ++j) {
  54. 	        // Truong hop khong chon kenh j de chuyen bat ki goi tin nao
  55. 	        F[i][j] = F[i][j - 1];
  56. 	        tr[i][j] = 0;
  57.  
  58. 	        // Truong hop chuyen k = {1, 2, ... i} goi tin tren kenh j
  59. 	        long long best = LL_INF;
  60. 	        int packNeeded = 0;
  61. 	        for(int k = 1; k <= i; ++k) if(F[i - k][j - 1] + cost[k][j] < best) {
  62. 	            best = F[i - k][j - 1] + cost[k][j];
  63. 	            packNeeded = k;
  64. 	        }
  65.  
  66. 	        // Tim min cua ca 2 truong hop
  67. 	        if(best < F[i][j - 1]) F[i][j] = best, tr[i][j] = packNeeded;
  68. 		}
  69.     }
  70.  
  71.     // Nghiem
  72.     return F[numPack][numChannel];
  73. }
  74.  
  75. void trace() {
  76.     int packRemain = numPack;
  77.  
  78.     for(int j = numChannel; j >= 1; --j) {
  79.         res[j] = tr[packRemain][j];
  80.         packRemain -= tr[packRemain][j];
  81.     }
  82.  
  83. 	for(int j = 1; j <= numChannel; ++j) cout << res[j] << "\n";
  84. }
  85.  
  86. void solve() {
  87.     cout << dp() << "\n";
  88.     trace();
  89. }
  90.  
  91. int main() {
  92.     setData();
  93.     read(); solve();
  94.  
  95.     return 0;
  96. }
Success #stdin #stdout 0.01s 5736KB
comments (?)
stdin
copy 
5 4
31 10 1  1
1  31 12 13
4  10 31 1
6  1  20 19
10 5  10 10
stdout
copy 
2
0
4
1
0
https://ideone.com/LdDJW1
language:
C++14 (clang 8.0)
created:
6 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!