HDU 1735字数統計-貪欲-[解題報告]C++

2113 ワード

欲張りは、最初に2つの0がある限り、その前の行の最後に何個連続した0があるかを判断し、前の行の最後に0の数を大きくから小さく並べ替える(破壊文字数を最小にするため、1(決定可能な文字数)に変換できる0の数を最大にする必要がある).最後に特殊な処理をして、最初の行の先頭と最後の行の末尾の0でいいです.
コードは次のとおりです.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int mess[10001][101];
struct Tom
{
    int num, zero;
} save[10001];
int cmp(const void *x, const void *y)
{
    return (*(struct Tom*)y).zero - (*(struct Tom*)x).zero;
}
int main()
{
#ifdef test
    freopen("sample.txt", "r", stdin);
#endif
    int m, n, l;
    while(scanf("%d%d%d", &n, &l, &m) != EOF)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<l; j++)
                scanf("%d", &mess[i][j]);
        }
        int cct=0;
        if(mess[0][0]==0&&mess[0][1]==0)
            mess[0][0]=mess[0][1]=2;//       0    
        for(int i=1; i<n; i++)
            if(mess[i][0]==0&&mess[i][1]==0)
            {
                save[cct].num = i;
                save[cct].zero = 0;
                for(int j=l-1; j>=0; j--)
                    if(mess[i-1][j]==0)
                        ++save[cct].zero;
                    else break;
                ++cct;
            }
        qsort(save, cct, sizeof(save[0]), cmp);
        for(int i=0; i<m-1; i++)
        {
            int ii = save[i].num;
            mess[ii][0]=mess[ii][1]=2;//     0     1
            for(int j=l-1; j>=0; j--)
                if(mess[ii-1][j]==0)
                    mess[ii-1][j] = 2;//      0     1
                else break;
        }
        int cct_zero=0;
        for(int i=l-1; i>=0; i--)
            if(mess[n-1][i]==0)//      0   
                mess[n-1][i]=2;
            else break;
        for(int i=0; i<n; i++)
            for(int j=0; j<l; j++)
                if(mess[i][j]==0)
                    ++cct_zero;
        printf("%d
", cct_zero); } return 0; }

変換元:http://www.acmerblog.com/hdu-1735-%E5%AD%97%E6%95%B0%E7%BB%9F%E8%AE%A1-2718/