bzoj 1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店【高精度+完全背包】

居然要用高精度！

懒得operator了，转移是裸的完全背包

#include<iostream>

#include<cstdio>

using namespace std;

int n,k,f[1005][45];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void clc(int x,int y)

{

	for(int i=1;i<=40;i++)

		f[x][i]+=f[y][i];

	for(int i=1;i<=40;i++)

	{

		f[x][i+1]+=f[x][i]/10;

		f[x][i]%=10;

	}

}

int main()

{

	n=read();k=read();

	f[0][1]=1;

    for(int i=1;i<=k;i++)

		for(int j=i;j<=n;j++)

			clc(j,j-i);

	int t=40;

	while(f[n][t]==0)

		t--;

	for(int i=t;i;i--)

		printf("%d",f[n][i]);

	return 0;

}

巴特西

bzoj 1655: [Usaco2006 Jan] Dollar Dayz 奶牛商店【高精度+完全背包】

最新文章

热门文章