華中科大校賽預賽1606 Naive

Naive
Time Limit: 3 Sec  Memory Limit: 128 MB
Submissions: 316  Solved: 36
Description
Give you a positive integer x, determine whether it is the sum of three positive cubic numbers.

Input
There’re several test cases. For each case:
Only one line containing an integer x (1≤x≤10^6)

Output
For each test case, print “Yes” if it is or “No” if it isn’t.
(See sample for more details)

Sample Input
1
3
10
Sample Output
No
Yes
Yes
HINT
Source
Problem Setter : Zhou Zhou

題意：  一個數是否可以表示成3個數的立方和   3個數可以為同一個數

思路 ：

一開始直接暴力 先輸入n  再去判斷n是不是符合條件   結果超時了
後來換了個思維  先找出符合條件的  再看n在不在  小水題把

[cpp] 
#include<stdio.h> 
#include<string.h> 
int a[105]; 
bool flag[1000000+10]; 
int main() 
{  www.2cto.com
    int i,j,k,n,mid; 
    for(i=1;i<=100;i++) 
        a[i]=i*i*i; 
    memset(flag,0,sizeof(flag)); 
    for(i=1;i<=100;i++) 
        for(j=i;j<=100;j++) 
            for(k=j;k<=100;k++) 
            { 
                  mid=a[i]+a[j]+a[k]; 
                if(mid<=1000000) 
                 flag[mid]=1; 
            } 
    while(scanf("%d",&n)!=EOF) 
    { 
        if(flag[n]) printf("Yes\n"); 
        else printf("No\n"); 
    } 
     
    return 0; 
}