洛谷P1586 四方定理
动态规划 + 离线
1 #include <bits/stdc++.h> 2 #define For(i,j,k) for(int i=j;i<=k;i++) 3 using namespace std ; 4 5 const int N = 35011 ; 6 int n,T,ans ; 7 int f[5][N],a[211] ; 8 9 inline int read() 10 { 11 int x = 0 , f = 1 ; 12 char ch = getchar() ; 13 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 14 while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 15 return x * f ; 16 } 17 18 inline void write(int x) 19 { 20 if(x<0) x=-x,putchar('-') ; 21 if(x>9) write(x/10) ; 22 putchar(x%10+48) ; 23 } 24 25 inline void writeln(int x) 26 { 27 write(x) ; putchar(' ') ; 28 } 29 30 int main() 31 { 32 T = read() ; 33 For(i,1,200) a[ i ] = i*i ; f[0][0] = 1 ; 34 For(i,1,200) 35 For(k,1,4) 36 For(j,a[i],32769) 37 f[k][j]+=f[k-1][j-a[i]] ; 38 while(T--) { 39 n = read() ; 40 ans = 0 ; 41 For(i,1,4) ans+=f[i][n] ; 42 writeln(ans) ; 43 } 44 return 0 ; 45 }