Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

完全背包可解...

Posted by JamesHarden at 2016-08-08 17:41:10 on Problem 2229
#include <iostream>
#include <cstdio>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const double pi = acos(-1.0);
const int mod = 1e9;

const int N =1e6+10;

int dp[N];

void Init()
{
	memset(dp,0,sizeof(dp));
	
	
	dp[0]=dp[1]=1;
	for(int i=1;i<=22;i++)
	{
		for(int j=2;j<=1000000;j++)
		{
			int v=1<<(i-1);
			if(j>=v)
				dp[j]=dp[j-v]+dp[j];
			while(dp[j]>mod)
				dp[j]-=mod;
		}
	}
}
int main()
{
	int n;
	Init();
	while(~scanf("%d",&n))
		printf("%d\n",dp[n]);
	return 0;
}




Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator