fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. static const int INF = 1e9;
  5.  
  6. int n, m;
  7. vector<string> A;          // đầu vào
  8. vector<string> B;          // kết quả (ban đầu = A)
  9.  
  10. // cnt[col][digit][i] = số hàng <= i có chữ số 'digit' ở cột col
  11. // i chạy 0..n, trong đó i=0 là 0 phần tử.
  12. vector<array<vector<int>,10>> cnt;
  13.  
  14. // số cột tối thiểu cần để tách L phần tử (cơ số 10)
  15. int needCols[105];
  16.  
  17. inline int blockCost(int col, int L, int R, int d){
  18.     // số hàng trong [L..R] KHÔNG phải d = (R-L+1) - (# d)
  19.     int have = cnt[col][d][R+1] - cnt[col][d][L];
  20.     return (R - L + 1) - have;
  21. }
  22.  
  23. // dp[col][L][R] = chi phí tối thiểu solve(col, L, R)
  24. // -1 nghĩa là chưa tính, >=0 là đã có; INF là không khả thi
  25. static int dp[401][105][105];
  26.  
  27. // Lưu cách chia khối cho state (col,L,R): vector of (endIndex, digit)
  28. // Các khối liên tiếp từ pos -> end với chữ số digit ở cột col
  29. struct Key {
  30.     int col,L,R;
  31.     bool operator==(Key const& o) const { return col==o.col && L==o.L && R==o.R; }
  32. };
  33. struct KeyHash {
  34.     size_t operator()(Key const& k) const {
  35.         return (k.col*1315423911u) ^ (k.L*2654435761u) ^ (k.R*97531u);
  36.     }
  37. };
  38. unordered_map<size_t, vector<pair<int,int>>> choiceMap;
  39. inline size_t packKey(int col,int L,int R){
  40.     // đóng gói key gọn gàng
  41.     return ( (size_t)col << 14 ) ^ ( (size_t)L << 7 ) ^ (size_t)R;
  42. }
  43.  
  44. // forward khai báo
  45. int solve(int col, int L, int R);
  46.  
  47. int solve(int col, int L, int R){
  48.     if (L==R) return 0;
  49.     if (col >= m) return INF;
  50.  
  51.     if (dp[col][L][R] != -1) return dp[col][L][R];
  52.  
  53.     int len = R - L + 1;
  54.     int remain = m - col;
  55.     if (needCols[len] > remain) return dp[col][L][R] = INF;
  56.  
  57.     // Quy hoạch động cục bộ để chia khối ở cột 'col' với chữ số tăng chặt
  58.     // go(pos, last_d): chi phí nhỏ nhất để phủ [pos..R], với chữ số của khối kế tiếp > last_d
  59.     // Lưu vết để dựng các khối
  60.     vector<array<int,11>> memo(R+2 - L);           // 11 giá trị last_d: -1..9 -> chỉ số +1
  61.     vector<array<int,11>> takeEnd(R+2 - L);
  62.     vector<array<int,11>> takeDigit(R+2 - L);
  63.     for (auto &row : memo) row.fill(-2); // -2 = chưa tính
  64.  
  65.     function<int(int,int)> go = [&](int pos, int lastdIdx)->int{
  66.         // lastdIdx: ánh xạ -1..9 -> 0..10 ; last_digit = lastdIdx-1
  67.         if (pos > R) return 0;
  68.         int &ret = memo[pos - L][lastdIdx];
  69.         if (ret != -2) return ret;
  70.         ret = INF; takeEnd[pos - L][lastdIdx] = -1; takeDigit[pos - L][lastdIdx] = -1;
  71.  
  72.         int last_d = lastdIdx - 1;
  73.         for (int d = last_d + 1; d <= 9; ++d){
  74.             // Chọn chữ số của KHỐI hiện tại là d, chọn điểm kết thúc khối j (pos..R)
  75.             for (int j = pos; j <= R; ++j){
  76.                 int c1 = blockCost(col, pos, j, d);
  77.                 int c2 = solve(col+1, pos, j);
  78.                 if (c2 >= INF) continue; // không khả thi
  79. int c3 = go(j+1, d+1); // next lastdIdx = d+1
  80.                 if (c1 + c2 + c3 < ret){
  81.                     ret = c1 + c2 + c3;
  82.                     takeEnd[pos - L][lastdIdx] = j;
  83.                     takeDigit[pos - L][lastdIdx] = d;
  84.                 }
  85.             }
  86.         }
  87.         return ret;
  88.     };
  89.  
  90.     int best = go(L, 0); // last_d = -1 -> idx = 0
  91.     dp[col][L][R] = best;
  92.     if (best >= INF) return best;
  93.  
  94.     // Lưu cách chia khối để dựng lời giải
  95.     vector<pair<int,int>> blocks;
  96.     int pos = L, lastIdx = 0;
  97.     while (pos <= R){
  98.         int j = takeEnd[pos - L][lastIdx];
  99.         int d = takeDigit[pos - L][lastIdx];
  100.         blocks.push_back({j, d});
  101.         lastIdx = d + 1;
  102.         pos = j + 1;
  103.     }
  104.     choiceMap[packKey(col,L,R)] = move(blocks);
  105.     return best;
  106. }
  107.  
  108. void buildSolution(int col, int L, int R){
  109.     if (L==R || col>=m) return;
  110.     auto it = choiceMap.find(packKey(col,L,R));
  111.     if (it == choiceMap.end()) return; // an toàn
  112.     auto &blocks = it->second;
  113.     int pos = L;
  114.     for (auto [j,d] : blocks){
  115.         // Gán chữ số cột 'col' cho đoạn [pos..j]
  116.         for (int i = pos; i <= j; ++i) B[i][col] = char('0' + d);
  117.         // Đệ quy sang cột tiếp theo trong đoạn
  118.         buildSolution(col+1, pos, j);
  119.         pos = j + 1;
  120.     }
  121. }
  122.  
  123. int main(){
  124.     ios::sync_with_stdio(false);
  125.     cin.tie(nullptr);
  126.  
  127.     if (!(cin >> n >> m)) return 0;
  128.     A.assign(n, "");
  129.     for (int i = 0; i < n; ++i){
  130.         string s; 
  131.         // đọc đủ m chữ số (bỏ qua khoảng trắng)
  132.         while ((int)A[i].size() < m && (cin >> s)){
  133.             for (char ch : s) if ('0'<=ch && ch<='9') A[i].push_back(ch);
  134.         }
  135.         if ((int)A[i].size() != m){
  136.             cerr << "Input hang " << i+1 << " khong du " << m << " chu so.\n";
  137.             return 0;
  138.         }
  139.     }
  140.  
  141.     // Nếu m cột không đủ để phân biệt n hàng (m quá nhỏ), không khả thi
  142.     auto minCols = [&](int L)->int{
  143.         if (L<=1) return 0;
  144.         int t=0; long long cap=1;
  145.         while (cap < L){ cap *= 10; ++t; }
  146.         return t;
  147.     };
  148.     if (m < minCols(n)){
  149.         // Không thể tăng chặt với cơ số 10 và chỉ m cột
  150.         // (đề thường sẽ không rơi vào TH này)
  151.         cout << "-1\n";
  152.         return 0;
  153.     }
  154.  
  155.     // needCols[L] cho mọi L ≤ n
  156.     needCols[0]=0;
  157.     for (int L=1; L<=n; ++L) needCols[L] = minCols(L);
  158.  
  159.     // Tiền xử lý prefix count cho từng cột
  160.     cnt.resize(m);
  161.     for (int c=0; c<m; ++c){
  162.         for (int d=0; d<10; ++d) cnt[c][d].assign(n+1, 0);
  163.         for (int i=0; i<n; ++i){
  164.             int dig = A[i][c]-'0';
  165.             for (int d=0; d<10; ++d){
  166.                 cnt[c][d][i+1] = cnt[c][d][i] + (d==dig);
  167.             }
  168.         }
  169.     }
  170.  
  171.     // Khởi tạo dp = -1
  172.     for (int c=0; c<m; ++c)
  173.         for (int i=0; i<n; ++i)
  174.             for (int j=0; j<n; ++j)
  175.                 dp[c][i][j] = -1;
  176.  
  177.     B = A;
  178.     int cost = solve(0, 0, n-1);
  179.     // (cost là số ô phải đổi tối thiểu; không in ra nếu đề không yêu cầu)
  180.     buildSolution(0, 0, n-1);
  181.     cout<<cost<<endl;
  182.     // In dãy bất kỳ đạt tối ưu: n dòng, mỗi dòng m chữ số
  183.     for (int i=0; i<n; ++i) cout << B[i] << '\n';
  184.     return 0;
  185. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
8 2
22
07
19
97
19
97
07
22
stdout
copy 
6
02
07
19
27
39
47
57
62
https://ideone.com/kVsUoD
language:
C++14 (gcc 8.3)
created:
17 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!