Zerojudge b797 V流星火雨 【DP】

tonyfang posted @ 2016年3月03日 16:55 in zerojudge with tags c++ OI , 350 阅读

题目大意:多次询问,求一个数的平方拆分个数

$TestCases \leq 40000, n \leq 40000$

平方拆分表示为,把一个数拆分成多个正整数的平方的和。

$Time Limit: 1s, Memory Limit: 32Mb$

【题解】

看起来像一个$O(n \sqrt{n})$的做法

我们先想$f[i,j]$表示,i可以拆分成,最大的数不大于j的个数。

$f[i,j]=\sum_{k=1}^{j} f[i-k \times k, k]$

然后我们发现可以用前缀和搞掉这个k

$f[i,j]=f[i,j-1]+f[i-j\times j,j]$

然后发现MLE了,因为有高精度。

然后我们发现,可以压掉j这维,发现是没有用的。

于是就好啦~

 

# include <stdio.h>
# include <math.h>
# include <iostream>
# include <algorithm>
# include <string.h>
using namespace std;

const int F=1e8;
struct bn {
	int s[8];
	bn() {
		memset(s,0,sizeof(s));
		s[0]=1;
	}
	bn(int x) {
		memset(s,0,sizeof(s));
		s[0]=1,s[1]=x;
	}
	int& operator[](const int i) {
		return s[i];
	}
	friend bn operator +(bn a, bn b) {
		bn c;
		c[0]=max(a[0],b[0]);
		for (int i=1;i<=c[0];++i) {
			c[i]+=a[i]+b[i];
			if(c[i]>F) {
				c[i+1]+=c[i]/F;
				c[i]=c[i]%F;
			}
		}
		while(c[c[0]+1]>0) ++c[0];
		return c;
	}
	void prt() {
		printf("%d",s[s[0]]);
		for (int i=s[0]-1;i>=1;--i) printf("%08d",s[i]);
		printf("\n");
	}
}f[40001];
struct tat
{
	int x,y,id;
}sm[40001];
bool cmp(tat a,tat b){return a.x<b.x;}
int main()
{
	int t,g;
	for (int i=1;i<=200;++i) f[0]=bn(1);
	for (int i=1;i<=200;++i) {
	  for (int j=i*i;j<=40000;++j)
			f[j]=f[j]+f[j-i*i];
	}
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		int x;
		scanf("%d",&x);
		f[x].prt();
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter