Algoogle

Algorithm for Programming Contest

AOJ 2546 Chocolate

Category: AOJ Tag: greedy

Chocolate

問題概要


解法


上が食べられてないとチョコを食べることが出来ないので一番上の行から順に見ていく.
また, そのことから2行目以降の味をあらかじめ1回反転させておけば
それぞれの行を独立に考えることができる.
あとは行の両端を見て甘い方を食べる.どちらも辛かったらどっちかを食べる.
食べたら隣の味を反転させる.
と貪欲に行がなくなるまで繰り返す.

コード


(2546.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>

#define rep(i,a) for(int i = 0; i < int(a); i++)

using namespace std;

int m, n;
int choco[128][128];

int main(){
    cin >> m >> n;
    int cnt = 0;
    rep(i,m){
        rep(j,n){
            cin >> choco[i][j];
            if(i) choco[i][j] = 1 - choco[i][j];
        }
        int tmp = 0, l = 0, r = n-1;
        while(l <= r){
            if(choco[i][l]){
                cnt++; l++;
                if(l < n)choco[i][l] = 1 - choco[i][l];
            }
            else{
                cnt += choco[i][r--];
                choco[i][r] = 1 - choco[i][r];
            }
        }
    }
    cout << cnt << endl;
}

Comments