#include <string>
#include <cstdio>
using namespace std;


const int MAX = 1000001;
char w[MAX][80];
int l[MAX];


int str_add(char *a, char *b, char *c1)
{
	char *c;
	int p, q;
	int i, j;
	int tmp;
	bool flag;
	c = new char[100]; 
	p = strlen(a)-1;
	q = strlen(b)-1;
	flag = false;
	j = 0;
	while (q >= 0) {
		tmp = a[p--] + b[q--] - 96;
		if (flag) {
			tmp++;
		}
		flag = false;
		if (tmp >= 10) {
			tmp -= 10;
			flag = true;
		}
		c[j++] = char(tmp+48);
	}
	while (p >= 0) {
		tmp = a[p--] - 48;
		if (flag) {
			tmp++;
		}
		flag = false;
		if (tmp >= 10) {
			tmp -= 10;
			flag = true;
		}
		c[j++] = char(tmp+48);
	}
	if (flag) {
		c[j++] = '1';
	}
	c[j] = '\0';
	j = 0;
	for (i=strlen(c)-1; i>=0; i--) {
		c1[j++] = c[i];
	}
	c1[j] = '\0';
	return 0;
}



int main()
{
	int n;
	int i, j, k;
	int len;
	char out[10];


	strcpy(w[1], "1");
	strcpy(w[2], "2");
	
	l[1] = 1;
	l[2] = 2;

	for (i=3; i<MAX; i++)
	{
		if (i%2 == 1) 
			strcpy(w[i], w[i-1]);
		else
		    str_add(w[i-2], w[i/2], w[i]);

		len = strlen(w[i]);
		j = 0;
		if (len >= 10)
		{
			j = len - 9;	
		}
		l[i] = atoi(w[i]+j);
	}
	
	while (scanf("%d", &n) != EOF)
	{	
		printf("%d\n", l[n]);
	}
	return 0;
}

• Re:为什么老是tle啊，我用高精度+dp。。。那位大侠帮帮忙，教教我怎么改？ (1513) czcpy 2011-02-10 13:27:01