mipt 006

水题。。直接DP。。

#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cstdlib>
using namespace std;
const int maxn=10000;
bool F[maxn]={0};
int main()
{
int n,x;F[0]=true;
for(int i=0;i<3;i++)
{
for(int t=maxn-1;t>=0;t–)
if(!F[t])
{
for(int j=0;j<100;j++)
{
x=j*j;if(x>t) break;
if(F[t-x]) {F[t]=true;break;}
}
}
}
cin>>n;
cout<<count(F,F+n+1,false)<<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>