UVA 12520 Square Garden

https://vjudge.net/problem/UVA-12520

题意：n*n网格中染色m个格子，染色格子的最长轮廓线

贪心

将格子分为4类

1、隔一个选一个，互不相邻的格子

2、4个角上的格子

3、边界除角的格子

4、内部的格子

4类从上到下依次选

1对答案有4的贡献

2对答案无贡献

3对答案有-2的贡献

4对答案有-4的贡献

对n奇偶分类讨论

当n为奇数时，在分左上角的格子在第1类还是第2类讨论

#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

    freopen("data.txt","r",stdin);

    freopen("my.txt","w",stdout);

    long long ans1,ans2,n,sum,rest,now,tmp;

    while(scanf("%lld%lld",&n,&sum)!=EOF)

    {

        if(!n) return ;

        if(n&)

        {

            if(sum<=n*n>> || sum<=n*n/+)

            {

                printf("%lld\n",sum<<);

                continue;

            }

            if(sum<=n*n/+) ans1=n*n/*;

            else

            {

                tmp=sum--n*n/;

                ans1=n*n/<<;

                rest=n/-<<;

                if(tmp<=rest) ans1-=tmp<<;

                else

                {

                    ans1-=rest<<;

                    tmp-=rest;

                    ans1-=tmp<<;

                }

            }

            ans2=n*n/+<<;

            now=n*n/+;

            rest=n/<<;

            if(sum-now<=rest) ans2-=sum-now<<;

            else

            {

                ans2-=rest<<;

                now+=rest;

                ans2-=sum-now<<;

            }

            printf("%lld\n",max(ans1,ans2));

        }

        else

        {

            if(sum<=n*n>>)

            {

                printf("%lld\n",sum<<);

                continue;

            }

            if(sum<=n*n/+)

            {

                printf("%lld\n",n*n/*);

                continue;

            }

            ans1=n*n>><<;

            tmp=sum-n*n/-;

            rest=n/-<<;

            if(tmp<=rest) ans1-=tmp<<;

            else

            {

                ans1-=rest<<;

                tmp-=rest;

                ans1-=tmp<<;

            }

            printf("%lld\n",ans1);

        }

    }

}

同一种思路大佬的写法就是短

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

ll l,n,a,b,c,ans;

ll cal()

{

    if(n<=a) return n*;

    if(n<=a+b) return a*;

    if(n<=a+b+c) return a*-(n-a-b)*;

    return a*-c*-(n-a-b-c)*;

}

int main()

{

    freopen("data.txt","r",stdin);

    freopen("std.txt","w",stdout);

    while(cin>>l>>n,l||n)

    {

        if(l%==)

        {

            a=l*l/;

            b=;

            c=l/-<<;

            ans=cal();

        }

        else

        {

            a=l*l/;

            b=l== ? :;

            c=l== ? :(l-)/*;

            ans=cal();

            a=l*l/+;

            b=;

            c=(l-)/*;

            ans=max(ans,cal());

        }

        cout<<ans<<endl;

    }

}

巴特西

UVA 12520 Square Garden

最新文章

热门文章