P1512 伊甸园日历游戏　

博弈论 DP 考试 记忆化搜索

题目

思路

初始状态是对方超过目标年月日就是己方赢，所以目标时间之后的范围都可以初始化为1。然后转移就是两种跳法如果有一种可以跳到对手必败的日期上，那这个日期就是必胜日期。一步一步逆推就好了。注意判闰年。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
int cal[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int g[115][14][33];
int jum1(int x,int y,int z)
{
    z++;
    int start=cal[y];
    if(x%4==0&&y==2&&x!=0)start=29;
    if(z>start)z=1,y++;
    if(y==13)y=1,x++;
    return g[x][y][z];
}
int jum2(int x,int y,int z)
{
    y++;
    if(y==13)y=1,x++;
    int start=cal[y];
    if(x%4==0&&y==2&&x!=0)start=29;
    if(start<z)return 1;
    return g[x][y][z];
}
int main()
{
    int year,month,day;
    for(int i=5;i<=31;i++)g[101][11][i]=1;
    for(int i=1;i<=31;i++)g[101][12][i]=1;
    for(int i=101;i>=0;i--)
    {
        for(int j=12;j>=1;j--)
        {
            int start=cal[j];if(i%4==0&&j==2&&i!=0)start=29;
            for(int k=start;k>=1;k--)
            {
                if(i==101&&j==11&&k>=4)continue;
                g[i][j][k]=!(jum1(i,j,k)&jum2(i,j,k));
            }
        }
    }
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>year>>month>>day;
        if(g[year-1900][month][day])cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}