116.cpp

平时acm训练时ac的源代码

//116
//Accepted 228 ms 61 kb 

#include <stdio.h>

int find(int *N, int k, int *sp, int *fnt)
{
	int t, i;
	if (N[k]==10000)
	{
		for (i=199; k-sp[i]<0 && i>=0; i--);
        if (i>=0)
        {
			if (k==sp[i])
			{
				N[k] = 1;
                fnt[k] = sp[i];
            }
            else
            {
				for (; i>=0; i--)
				{
					t = find(N, k-sp[i], sp, fnt) + 1;
					if (t<N[k])
                    {
						N[k] = t;
                        fnt[k] = k-sp[i];
                    }
                }
            }
		}
	}
	return N[k];
}

int main(void)
{
	int i, j, *f, y, *N, *fnt;
	int IN;
	scanf("%d", &IN);
	if (IN==1 || IN==2 || IN==4 || IN==0 || IN==7)
	{
		printf("0");
	}
	else
	{
		f = new int[1230];
		f[0] = 2;
		int c = 1;
		for (i=3; i<9924; i++)
		{
			if (0!=i%2)
			{
				y = 1;
				for (j=3; j<i; j+=2)
				{
					if (0==i%j)
					{
						y = 0;
						break;
					}
				}
				if (1==y)
				{
					f[c++] = i;
				}
			}
		}
		N = new int[IN+1];
		fnt = new int[IN+1];
		f[0] = f[f[0]-1];
		int c2 = 1;
		c++;
		for (i=3; i<c; i++)
		{
			if (0!=i%2)
			{
				y = 1;
				for (j=3; j<i; j+=2)
				{
					if (0==i%j)
					{
						y = 0;
						break;
					}
				}
				if (1==y)
				{
					f[c2++] = f[i-1];
				}
			}
		}
		for (i=0; i<=IN; i++)
		{
			N[i] = 10000;
		}
		f[c2] = 30000;
		int CNT;
		CNT = find(N, IN, f, fnt);
		printf("%d\n", CNT);
		for(;1!=N[IN];)
		{
			printf("%d ", IN-fnt[IN]);
			IN = fnt[IN];
		}
		printf("%d", fnt[IN]);
		delete N;
		delete fnt;
		delete f;
	}
	return 0;
}