广东工业大学第十五届文远知行杯程序设计竞赛 C 涂墙

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6+5;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;

int n,flag;
int f[N][6];
int dfs(int s,int num)
{
    if(f[s][num]!=-1) return f[s][num];
    if(s<num) return f[s][num] = 0;
    if(num == 1)  {
         if(s && s == sqrt(s)*sqrt(s)) return f[s][num] = 1;
         else return f[s][num] = 0;
    }
    for(int i=sqrt(s);i>=1;i--){
           f[s][num]=dfs(s-i*i,num-1);
           if(f[s][num]==1) return 1;
    }
    return f[s][num];
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    for(int i=0;i<N;i++){
        for(int j=0;j<10;j++){
            f[i][j] = -1;
        }
    }
    while(t--){
       scanf("%d",&n);
       if(f[n][5]==-1) f[n][5] = dfs(n,5);
       //if(!f[n][5]) printf("%d\n",n);
       printf("%s\n",f[n][5]?"YES":"NO");
    }
    return 0;
}