BeJing ICPC 2007 Color Squares

题目在UVA上。http://acm.uva.es/archive/nuevoportal/
一开始我的想法是搜索。。然后写了N个剪枝。。搞的累死。。结果却发现根本不行。。
我测了一下发现一组数据差不多0.2s。。但这玩意数据多的吓人。。TLE。。。
后来我感觉应该从这么多数据中找共同点。就是预处理一下。。
由于棋盘是一样的,所以能放的状态是有限的,
所有状态可以用它能分别放B-Y的个数和其需要的布数来表示,
只有步数最小的才予以考虑,那么只要开个4维数组记录所有状态就可以了。。、
由于没有剪枝,暴力搜出所有状态需要4s+。。但之后只要枚举4种颜色的个数就OK了。。
所以程序飞快,AC了(*^__^*) 嘻嘻
Code:
#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backconst int inf=~0U>>1;using namespace std;int D[10][10][10][10]={0};int w[4],W,cnt=0;int a[4]={0};int M[3][3]={0};bool check[4];const int di[]={0,1,0,-1},dj[]={1,0,-1,0};inline bool Legal(int i,int j){ return i>=0&&i<3&&j>=0&&j<3;}void Fill(int p,int i,int j,int s){ //cout<<p<<" "<<i<<" "<<j<<" "<<s<<endl; if(p==4) { int&x=D[a[0]][a[1]][a[2]][a[3]]; if(!x||x>s)x=s;cnt++; return; } if(i==3) { Fill(p+1,0,0,s); return; } int ii,jj; memset(check,0,sizeof(check)); rep(d,4) { ii=di[d]+i;jj=dj[d]+j; if(Legal(ii,jj)&&M[ii][jj]) check[M[ii][jj]-1]=true; } if(j==2)ii=i+1,jj=0; else ii=i,jj=j+1;bool c=true; rep(x,p)if(!check[x])c=false; Fill(p,ii,jj,s);if(!c)return; int om=M[i][j]; M[i][j]=p+1; a[p]++;if(om)a[om-1]–; Fill(p,ii,jj,s+1); a[p]–;if(om)a[om-1]++; M[i][j]=om;}int main(){ //freopen("in","r",stdin); Fill(0,0,0,0); for(int num=1;;num++) { rep(i,4)cin>>w[i];if(!w[0])break; cin>>W; int ans=100,s=0; for(int a=0;a<=9;a++) { s+=a*w[0]; for(int b=0;a+b<=9;b++) { s+=b*w[1]; for(int c=0;a+b+c<=9;c++) { s+=c*w[2]; for(int d=0;a+b+c+d<=9;d++) { s+=d*w[3];int x=D[a][b][d]; //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<s<<" "<<x<<endl; if(x&&s>=W)ans<?=x; s-=d*w[3]; } s-=c*w[2]; } s-=b*w[1]; } s-=a*w[0]; } cout<<"Case "<<num<<": "; if(ans==100)cout<<"Impossible"<<endl; else cout<<ans<<endl; }}

2 thoughts on “BeJing ICPC 2007 Color Squares

  1. 回复中国脑筋:额。。这个数组实际上也就是10*10*10*10,因为棋盘也就9个格子那么大囧。。实际上还是蛮快的。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>