P1512 伊甸园日历游戏

Eternity · 2019-03-09 00:06:49 · 个人记录

借着道题，说一下记忆化搜索

记忆化搜索=搜索的形式+dp的思想

思路

这道题主要的难点是在对于“必胜”的理解。印象中第一次说必胜是在博弈论的时候，就是nim游戏，到现在也没有弄懂。显然这道题是我想多了，我们需要倒退+顺推，因为我们是蒟蒻，所以并不能自己算出是否具有必胜的策略，所以这个时候样例就起了很大的作用，样例告诉我们 2011.11.4为必败时间，所以2011.11.3和2011.12.3就是必胜时间，通过这一点就可以进行顺推+逆推，算出所有可能，然后O（1）询问。其实这道题记忆化搜索的特征并不是很明显，应该算是一个创新题。

Code

#include<cstdio>
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int a[2010][13][40];
int n;
int main()
{
    int i,x,y,z;
    scanf("%d\n",&n);
    x=2004;y=11;z=4;
    a[x][y][z]=0;
    while (!(x==1900&&y==1&&z==1))
    {
        if (a[x][y][z]==0) 
        {
            if (y==1&&z==1) a[x-1][12][31]=1;
            else
            if (z==1)
            {
              if (x%4==0&&x!=1900&&y==3) a[x][y-1][month[y-1]+1]=1;
              else a[x][y-1][month[y-1]]=1;
            }
            else a[x][y][z-1]=1;
            if (y==1)  a[x-1][12][z]=1;
            else if (x%4==0&&x!=1900&&y==3&&z<=month[2]+1) a[x][2][z]=1; 
            else if (z<=month[y-1]) a[x][y-1][z]=1;
        }
        if (y==1&&z==1){x--;y=12;z=31;} 
        else if (z==1)
        {
          if (x%4==0&&x!=1900&&y==3){y=2;z=29;}
              else {y--;z=month[y];}
        }
        else z--;
        }
    for(i=1;i<=n;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        if (a[x][y][z]==1) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}