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 0;if(n&1){if(sum<=n*n>>1 || sum<=n*n/2+1) {printf("%lld\n",sum<<2);continue;}if(sum<=n*n/2+4) ans1=n*n/2*4;else{tmp=sum-4-n*n/2;ans1=n*n/2<<2;rest=n/2-1<<2;if(tmp<=rest) ans1-=tmp<<1;else{ans1-=rest<<1;tmp-=rest;ans1-=tmp<<2;}}ans2=n*n/2+1<<2;now=n*n/2+1;rest=n/2<<2;if(sum-now<=rest) ans2-=sum-now<<1;else{ans2-=rest<<1;now+=rest;ans2-=sum-now<<2;}printf("%lld\n",max(ans1,ans2));}else{if(sum<=n*n>>1){printf("%lld\n",sum<<2);continue;}if(sum<=n*n/2+2){printf("%lld\n",n*n/2*4);continue;}ans1=n*n>>1<<2;tmp=sum-n*n/2-2;rest=n/2-1<<2;if(tmp<=rest) ans1-=tmp<<1;else{ans1-=rest<<1;tmp-=rest;ans1-=tmp<<2;}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*4;if(n<=a+b) return a*4;if(n<=a+b+c) return a*4-(n-a-b)*2;return a*4-c*2-(n-a-b-c)*4; } int main() {freopen("data.txt","r",stdin);freopen("std.txt","w",stdout);while(cin>>l>>n,l||n){if(l%2==0){a=l*l/2;b=2;c=l/2-1<<2;ans=cal();}else{a=l*l/2;b=l==1 ? 1:4;c=l==0 ? 0:(l-3)/2*4;ans=cal();a=l*l/2+1;b=0;c=(l-1)/2*4;ans=max(ans,cal());}cout<<ans<<endl;} }
