P171SUMD – ptit

Đề bài:

Thuật toán:

  • Ưu tiên di chuyển hàng trước nếu m < n và ngược lại.
  • Sử dụng thuật toán tham lam trừ từng hàng và từng từng cột.

Code:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 200;
const int oo = 1000;
int m, n, i, j, g[MAXN][MAXN], kt, mi, tam, dadoi;
vector<int> H, C;
 
void xulyhang() {
    for (int i=1; i<=m; i++) {
        mi = oo;
        for (int j=1; j<=n; j++) mi = min(mi, g[i][j]);
        for (int j=1; j<=mi; j++) H.push_back(i);
        for (int j=1; j<=n; j++) g[i][j]-=mi;
    }
}
 
void xulycot() {
    for (int j=1; j<=n; j++) {
        mi = oo;
        for (int i=1; i<=m; i++) mi = min(mi, g[i][j]);
        for (int i=1; i<=mi; i++) C.push_back(j);
        for (int i=1; i<=m; i++) g[i][j]-=mi;
    }
}
 
int main() {
    cin >> m >> n;
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++) cin >> g[i][j];
    kt = 1;
    if (m < n) {
        xulyhang();
        xulycot();
    }
    else {
        xulycot();
        xulyhang();
    }
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
        if (g[i][j]!=0) kt = 0;
    if (kt==0) cout << -1;
    else {
            cout << C.size()+H.size() << endl;
            for (int i=0; i<H.size(); i++) cout << "H " << H[i] << endl;
            for (int i=0; i<C.size(); i++) cout << "C " << C[i] << endl;
    }
	return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*