1024.cpp

ZOJ 动态规划算法题目入门与提高 源代码

#include<vector>
#include<iostream>
using namespace std;
class data{
   public:
     int y,m,d;
     data(int a,int b,int c){y=a;m=b;d=c;}
	 data(const data & s){y=s.y;m=s.m;d=s.d;}
};
int nv(int y){
   if(y==1900) return 0;
   else if(y%4==0) return 1;
   else return 0;
}
data subday(data c){
   if(c.d!=1) c.d-=1;
   else{
     if(c.m==12||c.m==10||c.m==7||c.m==5) {c.d=30;c.m-=1;}
     else if(c.m==11||c.m==9||c.m==8||c.m==6||c.m==4||c.m==2){c.d=31;c.m-=1;}
     else if(c.m==1) {c.m=12;c.d=31;c.y-=1;}
     else{
          if(nv(c.y)) c.d=29; else c.d=28; 
		  c.m-=1;
     }
   }
   return c;
}
data submos(data  c,int & flag){
   if(c.m==11||c.m==9||c.m==8||c.m==6||c.m==4||c.m==2) {c.m-=1;flag=1;}
   else if(c.m==1){c.m=12;c.y-=1;flag=1;}
   else if(c.m==12){if(c.d!=31){c.m=11;flag=1;} else flag=0;}
   else if(c.m==10){if(c.d!=31){c.m=9;flag=1;} else flag=0;}
   else if(c.m==7){if(c.d!=31){c.m=6;flag=1;} else flag=0;}
   else if(c.m==5){if(c.d!=31){c.m=4;flag=1;} else flag=0;}
   else {
     if(c.d<=28){c.m=2;flag=1;}
     else if(c.d>29) flag=0;
     else {
          if(nv(c.y)){c.m=2;flag=1;}
          else flag=0;
     }
   }
   return c;
}
int main(){
  //int vec[102][13][32];
  int y,m,d,flag,i,j,k,l;
/*  for(i=0;i<102;i++)
	  for(j=0;j<13;j++)
		  for(k=0;k<32;k++)
			  vec[i][j][k]=1;*/
  vector<int> aaaaa(32,1);
  vector<vector<int> > bbbbb(13,aaaaa);
  vector<vector<vector<int> > > vec(102,bbbbb);
  //vec[101][11][4]=0;
  data adata(2001,11,4);
  while(1){
	   vec[adata.y-1900][adata.m][adata.d]=2;
       data aaa=subday(adata),bbb=submos(adata,flag);
	   if(aaa.y>=1900) vec[aaa.y-1900][aaa.m][aaa.d]=0;
       if(bbb.y>=1900&&flag) vec[bbb.y-1900][bbb.m][bbb.d]=0;
	   do{
            adata=subday(adata);
            if(adata.y<1900) goto end;
	   }while(vec[adata.y-1900][adata.m][adata.d]==0);
  }
  end:
  cin>>l;
  for(int _l=0;_l<l;_l++){
     cin>>y>>m>>d;
	 if(vec[y-1900][m][d]==0) cout<<"YES\n";
	 else cout<<"NO\n";
  }
}